Let the input be an array of $n$ elements, with $k$ sets $S_1,...,S_k$ such that each set has $\frac n k$ elements. The elements in each $S_i$ are larger than the elements in $S_{i-1}$.

  1. Find an algorithm that sorts the input in $O(n\log (\frac n k ))$ runtime.

  2. Find a lower bound for the minimal amount of comparisons in the worst case.

  1. is pretty simple I think:

    for each S_i

But with 2. I get results that can't be right: in the worst case there would have to be at least $(\frac n k )!$ comparisons for each $S_i$ because the algorithm will have to pass each combination at least once, also, this is the amount of leaves at the lowest level of the decision tree.

This gives: $T_{worst}(n) = \Omega (k(\frac n k )!)$ which is a lot larger than $O(n\log (\frac n k ))$. So what am I doing wrong here?


If a decision tree has at least $m$ leaves then its height is at least $\log_2 m$. It is the height that bounds the number of comparisons rather than the number of leaves. In your case there are $(n/k)!^k$ leaves, and so $\Omega(\log[(n/k)!^k]) = \Omega(n\log(n/k))$ comparisons.

  • $\begingroup$ Why does the height bounds it and not the number of leaves? The algorithm needs to try all the combinations in the worst case. $\endgroup$ – shinzou Nov 30 '15 at 5:48
  • 1
    $\begingroup$ @kuhaku A computation path doesn't explore the complete tree but only a single path. $\endgroup$ – Yuval Filmus Nov 30 '15 at 6:01

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.