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.