# Lower bound on comparison-based sorting

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.

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)}$$.
• 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. Jul 10, 2020 at 5:03