1
$\begingroup$

I have come across a proof where a certain function ("compute a straight skeleton") is shown to take $\Omega(n \log n)$ time by reducing the problem of sorting to it. The overhead for the reduction itself is linear, thus negligible.

Now my question is: is this a valid argument?


The original proof appears in: Huber - Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice, page 19, last paragraph.

In summary:

Given a list of $n$ natural numbers, the author constructs a "Polygon with holes" $P$ of structural size $O(n)$ in linear time. The algorithm then computes a straight skeleton $S(P)$, which can be traversed to enumerate the original numbers in sorted order (with constant overhead per number). Thus, the problem of sorting is reduced to computing $S(P)$. The author claims that this implies computing $S(P)$ is in $\Omega(n \log n)$ due to the bound for sorting.


It is well know that comparison-based sorting algorithms have $\Omega(n \log n)$ worst-case bounds. However, there are $O(n)$ sorting algorithms such as radix sort or bucket sort which aren't based on comparisons and for which this restriction doesn't apply. As far as I can tell, these are all restricted to certain domains, such as fixed-length integers or strings.

I assume generalizing these algorithms to unrestricted domains would reveal hidden costs. If we consider arbitrary integers, some operations which are assumed to be constant cost would actually be logarithmic in the size of the integer. I don't know, however, if this necessarily has to be the case for all possible sorting algorithms.

I think the author's construction could be used for sorting real numbers (possibly requiring a variable-length encoding), if this strengthens the requirement on the sorting enough to rule out any $O(n)$ (or $o(n \log n)$) sorting algorithms.

Are there any information theoretic arguments showing that, for fully general inputs and all operations strictly accounted for, at least $\Omega(n \log n)$ basic units of work (whether they be comparison or something else) are always needed? If not, does that mean the argument of "by reduction from sorting" doesn't strictly prove a lower bound stronger than $\Omega(n)$?

$\endgroup$
  • $\begingroup$ I've edited it accordingly. $\endgroup$ – Andre Jan 12 '17 at 9:03
  • 1
    $\begingroup$ "As far as I can tell, these [non-comparison sorts] are all restricted to certain domains, such as fixed-length integers or strings" --- actually the O(n ln n) for comparison sorts is only valid when the key lengths 'k' are all much smaller than 'n'. Otherwise the complexity is O(kn ln kn). +++ The complexity for Counting Sort is O(n+r) where r is the range (max-min) of the integers. +++ The complexity for LSD Radix is O(n+k/d) where 'k' is as above and 'd' is the digit size. $\endgroup$ – Craig Hicks Nov 27 '17 at 6:31
2
$\begingroup$

It's not a valid argument. What it does prove is that any comparison-based algorithm for Problem X must use at least $\Omega(n \log n)$ comparisons. (There is a known algorithm for integer sorting whose running time is $O(n \sqrt{\log \log n})$, in some models of computation, but it is not a purely comparison-based algorithm; see here.)

$\endgroup$
  • $\begingroup$ Yes, I meant the question like you assumed and have edited it accordingly. Also see my updated description. Could the algorithm you referenced be applied to real numbers (with arbitrary precision encoding) too? $\endgroup$ – Andre Jan 12 '17 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.