1
$\begingroup$

Assume an array $X=[x_1,...,x_n]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x_1 \le ... \le x_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\log n)$, while in some models of computation, e.g., random-access machines, this can be reduced to $\mathcal{O}(n)$ under specific circumstances.

However, the statement

There exists an algorithm that sorts any $X$ in $\mathcal{O}(\log n)$ time in the worst-case.

seems like nonsense to me. Is there some rigorous refutation of the above statement? I am aware of high-level arguments such as

  • "Just reading $X$ takes at least $\mathcal{O}(n)$ time"
  • "The sorted array needs $\mathcal{O}(n)$ space, and the runtime of an algorithm is bounded from below by the space it needs"

but these arguments aren't really helpful for a rigorous refutation of the above statement. According to my understanding, such a refutation would need to show that

for every algorithm $A$ in every reasonable model of computation, there exists an $X$ such that $A$ does not correctly sort $X$ in $\mathcal{O}(\log n)$ time.

This is not homework, and I do not have a source for the above statement.

$\endgroup$
1
  • $\begingroup$ Note that the sorting problem is at least hard as decision problem $X$ is sorted or not. $\endgroup$
    – Jut
    Sep 2 at 11:34
2
$\begingroup$

The first argument does help with a rigorous refutation for the statement.

If you want to really be formal, here is how you should approach it (its not a formal proof, but more of a sketch for how you should prove it formally):

Assume towards contradiction there is some algorithm $A$ that solve this question in $o(n)$ time. Since the run-time of $A$ is asymptotically smaller than $n$, then, when taking a big enough $n$, for any $X$ with $n$ elements there must be at least two indices that $A$ doesn't check. Therefore, if we swap the values (or at least, change the values so now any sorted array will have them in opposite order) - since $A$ never checked them, the computation history must be the same, and thus also all swaps it did were the same. However - $A$ never accessed those two indices and hence also never swapped them back to their correct position - which means that either the final array on the original $X$, or on the changed $X$, must be incorrect. Therefore, we get a contradiction to that we assumed $A$ solves this question, and hence $A$ must work in at least $\Omega(n)$ in order to actually sort.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks. I guess the key point that I missed is the equal computation history. $\endgroup$
    – mto_19
    Sep 2 at 10:20
  • $\begingroup$ @mto_19 notice that there is actually a small caveat: if we swap two elements with the same value. In this case, just increase one of them by one and do the process again. $\endgroup$
    – nir shahar
    Sep 2 at 10:29
1
$\begingroup$

This would depend on context. You can't do a comparison based sort with less than log (n!) comparisons, and that's $\Theta(n \log n)$. But the statement doesn't say "comparisons", it says "time".

With unlimited resources, say with $n^2$ processors that can all run in parallel, it might very well be possible. Finding the maximum of n values in O (log n) is quite easy with n processors. Sorting in O (log n) will be harder and needs more cleverness than I have in 5 minutes, but I wouldn't be surprised if it can be done.

$\endgroup$

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.