8.1-3

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$?
using the formula from theorem 8.1
$$n! \leq l \leq 2^h$$ $$ n!/2 \leq n! \leq l \leq 2^h$$ taking logs on both sides $$ log (n!/2) \leq log (2^h)$$ $$ log (n!) - log 2 \leq log (2^h)$$ $$ log (n!) - 1 \leq log (2^h)$$ $$ log (n!) - 1 \leq h $$ $$ log (n!) - 1 \leq log(n!) \leq h $$ $$log(n!) \leq h $$ $$log(n!) = h $$ $$ \Omega(n log(n)) = h $$ b)fraction of $1/n$ of the inputs of length n?
$$ n!/n \leq n! \leq l \leq 2^h$$ $$ n!/n \leq 2^h$$ taking logs on both sides $$ log (n!/n) \leq log 2^h$$ $$ log n! - log n \leq h$$ $$ log n! - log n \leq h$$ c.What about a fraction $1/2^n$ $$ n!/2^n \leq n! \leq l \leq 2^h$$ taking log on both sides $$ log n!/2^n \leq log 2^h $$ $$ log n!/2^n \leq h $$ $$ log n! - log 2^n \leq h $$ $$ log n! - n \leq h $$