Auto comment: topic has been updated by 1.LaZyPersoN (previous revision, new revision, compare).

Auto comment: topic has been updated by 1.LaZyPersoN (previous revision, new revision, compare).

It's parallel computing complexity, that's indeed O(log^2) time complexity but it's O(n log^2) for compute complexity that means if you have a processor with a lot of cores that can do many computations at the same time you can do the computation faster but on codeforces you'll have access to only one core the only kind of parallelization I'm aware of on codeforces is vectorization you can look at https://mirror.codeforces.com/blog/entry/98594 to know more. but basically for general sorting you'll never go faster than O(nlogn)

$$$O(\log^2 n)$$$ assuming comparisons that are not affected by each other are done simultaneously. Say, we want to sort an array with $$$4$$$ elements. We can do that by (comparing and) swapping indices $$$(3,4), (1,2), (2,4), (1,3), (2,3)$$$. This has $$$5$$$ comparisons, but parallelism makes it possible to run $$$(3,4)$$$ and $$$(1,2)$$$ simultaneously, for example. (However, we can not run $$$(3,4)$$$ and $$$(2,4)$$$ simultaneously, the former must be run strictly before the latter. This is due to a lock in using the resource.) So, while there are $$$5$$$ comparisons it will take $$$3$$$ "runs" of comparisons. $$$O(\log^2 n)$$$ in this context means the number of "runs" in the example. Of course, if we run the same algorithm sequentially, the time complexity is not $$$O(\log^2 n)$$$, it is in fact $$$O(n \log^2 n)$$$.

Yes this is true it will only be working when your computer will have N prcoessors like maybe a gpu or just hasmany cpus like amd threadripper or intel xeon or smth

Sadly codeforces will not have this feature of many processors for now but maybe in the future??? @MikeMirzayanov ???