Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $A$ to completely sorted in $O(n\log (n/k))$. $n$ is the size of the array, while $k$ is another non-constant parameter given. I want to get a contradiction. Here is my reasoning:

Running the first algorithm followed by the second completely sorts the array, and takes

$$o(n\log k)\ +\ O(n\log(n/k)) = o(n\log k\ +\ n\log(n/k)) =$$ $$o(n(\log k\ +\ \log(n/k))) = o(n\log (k \times n/k)) = o(n\log n)$$

which is a contradiction to the known lower bound to comparison-based sorting algorithms.

My question is: Is my reasoning correct? Why or why not? I've tried to prove it using the definitions, but I'm stuck.


  • 2
    $\begingroup$ o + O = o is immediately wrong. $\endgroup$ – gnasher729 Sep 14 '16 at 8:09

No. You are misusing Landau notation.

  1. $o(f) + O(g) \not\subseteq o(f + g)$ even if $f \in O(g)$. The best you can get is $O(f + g)$. If $g \in o(f)$, you get $o(f)$.

  2. $\log k$ and $\log n$ are incomparable as long as you can not put $k$ and $n$ in some kind of relation.

Assuming that $k \in \omega(1) \cap O(n)$, you can show that both $o(n \log k) \subseteq o(n \log n)$ and $O(n \log (n/k)) \subseteq o(n \log n)$. Then, we would indeed deduce that the proposed algorithm would take $o(n \log n)$ comparisons, contradicting the known lower bound.


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.