4 ms·
There may be some difference in accounting. The recursion depth of Blelloch's recursive function you linked to is O(log n), but it uses an operation that canno
by shasta 16y ago
There may be some difference in accounting. The recursion depth of Blelloch's recursive function you linked to is O(log n), but it uses an operation that cannot be implemented in constant time: partitioning the elements into those greater and less than the pivot. I'd guess that operation is itself O(log n), which would account for the O(log^2 n).
- kragen 16y ago"Depth" and "recursion depth" are not the same thing. Quicksort partitioning normally takes O(N) time, but it can be in some sense perfectly parallelized once you have the pivot.
- cousin_it 16y agoBy "in some sense", do you mean it can be parallelized to O(1) time as long as you don't have to actually build up the data structures that result from partitioning (e.g. arrays)? Then it's not clear to me why this assumption is applicable to quicksorting an array. Doesn't it call for some non-obvious representation of intermediate results?
- kragen 16y agoI'm out of my depth (heh) commenting here, but I think it depends on what kind of communications infrastructure you're assuming.
- shasta 16y agoBut isn't recursion depth the same as depth if each operation in your recursive function is constant time (except for the recursing bits)? Thus you can look at recursive depth as computing depth modulo the bits you compute in your function at a fixed level. I was speculating that partitioning would require O(log n) parallel steps. Can you give details or provide a link to achieving it constant depth?