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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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)}$.

Improve this answer
$\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, 2020 at 5:03
  • $\begingroup$ It's not only about the number of leaves. It's also about their depth. $\endgroup$
    – Yuval Filmus
    Jul 10, 2020 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.