1
$\begingroup$

I have a question from one of the exercises in CLRS.

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction $1/2^n$?

I have arrived at the step where for a linear time sorter, there will we $2^n$ nodes in the decision tree, which is smaller than the $n!$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $n!$ inputs of length $n$". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $n$ will have $n!$ possible permutations.

$\endgroup$
0
1
$\begingroup$

If there is a comparison sort whose running time is $f(n)$ on $g(n)$ of the inputs, then there are at least $g(n)$ leaves at depth at most $f(n)$, and so $g(n) \leq 2^{f(n)}$.

$\endgroup$
2
  • $\begingroup$ Oh so what we are doing is lower bounding the number of leaves? But wouldn't it make sense that for a input of length $n$, even if the input is $1/2$ of all possible $n!$ permutations, to have number of leaves exactly as $n!$? Pardon me as I don't quite understand why we should have it as: at least $g(n)$ leaves. $\endgroup$ – Ken Gondor Jul 10 '20 at 5:03
  • $\begingroup$ It's not only about the number of leaves. It's also about their depth. $\endgroup$ – Yuval Filmus Jul 10 '20 at 11:24

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.