4 ms·

The post says that the depth of quicksort is O(log^2 n). Blelloch's list of NESL algorithms gives a depth of O(log n) instead: http://www.cs.cmu.edu/~scandal/n

The post says that the depth of quicksort is O(log^2 n). Blelloch's list of NESL algorithms gives a depth of O(log n) instead: http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicksort http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicks... Or do I misunderstand something?

deleted 16y ago
[deleted]
- JoachimSchipper 16y ago
  I've never seen log^2 x mean anything except (log x)^2; you're thinking of ^2log x.
  - pessimizer 16y ago
    I've never seen log^2 x mean (log x)^2. Common notation?
    - pmjordan 16y ago
      Yes. It's maybe more frequently seen on other functions such as trig functions (e.g. the identity sin²α+cos²α=1) but it crops up a lot on logarithms in computational complexity (as here). I've certainly never seen it used to mean anything else. As grandpa says, base is written as subscript.
    - grandpa 16y ago
      The base is usually a subscript: log_2(x), and the square is a superscript, log^2(x). Example of the superscript notation meaning squared: http://www.springerlink.com/content/7n7219tcyxr81gxc/ http://www.springerlink.com/content/7n7219tcyxr81gxc/
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 ago
    By "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 ago
      I'm out of my depth (heh) commenting here, but I think it depends on what kind of communications infrastructure you're assuming.
  - shasta 16y ago
    But 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?
kragen 16y ago
Quicksort takes O(N log N) time when comparing two keys is constant time. But as N → ∞, if your keys continue to have a fixed number of bits, you're going to have a lot of duplicate keys. (Consider sorting four billion 8-bit bytes.) In that case you can do better than Quicksort; you can simply partition the data in O(N) time among the unique keys, then sort the keys in O(1) time, then concatenate the partitions in O(N) time. So if you have to have unique keys, each comparison is going to take O(log N) time instead of O(1) time, so the overall algorithm takes O(N log² N) time. On the other hand, this is somewhat of a theoretical consideration if your keys are more than about 4–6 bytes long in the first place, since it's not very practical to store 2⁴⁸ records. But 2⁴⁸ is a long way from ∞, and if you're going to fudge by treating the theoretical factor of log N as constant, you might as well claim that Quicksort is O(N) with a constant of, say, less than 100 comparisons per key. I don't know anything about analyzing parallel quicksort, but maybe this key-comparison-time factor explains it? Because it seems like key comparisons would pretty much have to be serialized on Quicksort's critical path, no?

deleted 16y ago

[deleted]

JoachimSchipper 16y ago
I've never seen log^2 x mean anything except (log x)^2; you're thinking of ^2log x.
- pessimizer 16y ago
  I've never seen log^2 x mean (log x)^2. Common notation?
  - pmjordan 16y ago
    Yes. It's maybe more frequently seen on other functions such as trig functions (e.g. the identity sin²α+cos²α=1) but it crops up a lot on logarithms in computational complexity (as here). I've certainly never seen it used to mean anything else. As grandpa says, base is written as subscript.
  - grandpa 16y ago
    The base is usually a subscript: log_2(x), and the square is a superscript, log^2(x). Example of the superscript notation meaning squared: http://www.springerlink.com/content/7n7219tcyxr81gxc/ http://www.springerlink.com/content/7n7219tcyxr81gxc/

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 ago
  By "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 ago
    I'm out of my depth (heh) commenting here, but I think it depends on what kind of communications infrastructure you're assuming.
- shasta 16y ago
  But 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?

kragen 16y ago

Quicksort takes O(N log N) time when comparing two keys is constant time. But as N → ∞, if your keys continue to have a fixed number of bits, you're going to have a lot of duplicate keys. (Consider sorting four billion 8-bit bytes.) In that case you can do better than Quicksort; you can simply partition the data in O(N) time among the unique keys, then sort the keys in O(1) time, then concatenate the partitions in O(N) time. So if you have to have unique keys, each comparison is going to take O(log N) time instead of O(1) time, so the overall algorithm takes O(N log² N) time. On the other hand, this is somewhat of a theoretical consideration if your keys are more than about 4–6 bytes long in the first place, since it's not very practical to store 2⁴⁸ records. But 2⁴⁸ is a long way from ∞, and if you're going to fudge by treating the theoretical factor of log N as constant, you might as well claim that Quicksort is O(N) with a constant of, say, less than 100 comparisons per key. I don't know anything about analyzing parallel quicksort, but maybe this key-comparison-time factor explains it? Because it seems like key comparisons would pretty much have to be serialized on Quicksort's critical path, no?