1
$\begingroup$

My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?

In more details: we know that sorting using comparison have the achievable lower bound of $O(n\ln n)$ where $n$ is the number of items to be sorted. Now the question of superlinear and sublinear is dependent on what is considered the size of the input, and I am not sure if $n$ is the size here. We have 2 cases:

(a) The input is a full acyclic graph describing the comparison relation. In this case the input size is actually $O(n^{2})$ and the problem is sublinear.

(b) The input is just the item to be sorted, plus the description of a Turing machine that will perform the comparison. Then the input size is $O(n)$ and the problem is superlinear.

Can anyone clarify what is the consensus on this? Some people tell me that sorting with comparison is an example of a problem with a nontrivial lower bound (ie. the lower bound stronger than just by looking at how much information do the algorithm need to know). However, it seemed to me that in fact this is one example where figure out how much information you need is the crux of the problem, and not any combinatorial nature of Turing machine. Thanks.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Could you elaborate on this "comparison relation" graph? If I understand it correctly, its size should just be a function of the alphabet size, which is technically constant. $\endgroup$ – jadhachem Dec 19 '16 at 6:41
  • $\begingroup$ "lower bound of O(n ln n)" -- that doesn't make any sense; you are saying something like "this is at least no more than 3". You want to use $\Omega$. $\endgroup$ – Raphael♦ Dec 19 '16 at 13:32
  • $\begingroup$ What is $n$? (This is central here, as my answer shows.) $\endgroup$ – Raphael♦ Dec 19 '16 at 13:38
4
$\begingroup$

In complexity theory, the input size is by convention (or definition, really) the number of cells the input takes up on a Turing machine tape.

The famous $\Omega(n \log n)$ bound does not adhere to this convention, though; $n$ is not input size but number of elements here. The input is (in general) longer than that since every element will have to be encoded on the tape in some way.

Generally, in sorting we consider the input to be the array (or list) of elements to be sorted. We don't pass the comparison matrix.

But you touch on an important point: complexity statements depend on machine model and input encoding. We usually default to TMs or RAMs depending on context and "reasonable" (i.e. not wasteful) encodings, but if there is any chance for ambiguity you need to state all the parameters.

For instance, the input size of sorting is $n$ is you consider RAMs with unit cost measure!

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "$n$ is not input size but number of elements here." In typical use cases, these are basically the same since the size of each element is constant (e.g., 32 bits). $\endgroup$ – jadhachem Dec 19 '16 at 19:10
  • $\begingroup$ @jadhachem In practice, everything is bounded by finite constants so all costs are in $O(1)$. That's not terribly interesting. And if you make the models more interesting (and relevant!), you can not always consider numbers to have constant size. See also here. Anyway, we're talking formal models here, not reality. (Your point does have merit, of course; that's why we use unit-cost RAM in algorithm analysis.) $\endgroup$ – Raphael♦ Dec 19 '16 at 19:18
  • 1
    $\begingroup$ That's true! I was generally thinking of why sorting can be $n\log n$ in the input size (and hence why the distinction is not always made), but I see that my comment was inaccurate. Thanks for the link, good read! $\endgroup$ – jadhachem Dec 19 '16 at 20:40

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.