simulation theory - how is the sorting only log(p)?

StackOverflow https://stackoverflow.com/questions/22645112

Question

In the proof of simulation theory : simulating concurrent write : "a p-processors in a crcw algorithm can be no more then log(p)time faster then the best erew algorithm for the same problem"

enter image description here

can anyone explain me why it takes only log(p) to sort the array by the first component in the simulation proof and not O(plogp)?

Was it helpful?

Solution

The sorting is accomplished in parallel with a log-depth sorting network. The AKS construction is a good example of a galactic algorithm. Batcher's bitonic sorting network with depth log^2 n is more reasonable in practice.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top