title: Lower bounds on comparison sorts for a small fraction of inputs?
body: <p>Can someone please walk me through mathematical part of the solution of the following problem.</p>
  
  <p>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)?</p>
  
  <p>Solution:</p>
  
  <p>If the sort runs in linear time for m input permutations, then the height h of the
  portion of the decision tree consisting of the m corresponding leaves and their
  ancestors is linear.
  Use the same argument as in the proof of Theorem 8.1 to show that this is impossible
  for m = n!/2, n!/n, or n!/2n.
  We have 2^h ≥ m, which gives us h ≥ lgm. For all the possible ms given here,
  lgm = Ω(n lg n), hence h = Ω(n lg n).
  In particular,</p>
  
  <pre><code>    lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1
      lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n
      lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n
  </code></pre>