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.Thanks.
Adding Big-O and little-o notation to get a little-o
proof techniques;landau notation;lower bounds
No. You are misusing Landau notation.$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)$.$\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.