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 &quot;for at least half of the $n!$ inputs of length $n$&quot;. 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)}$.