Name: ____________________________________________________ Alpha: _____________________

A crucial fact in our derivation of the lower bound on the worst-case time for comparison-based sorting was this: if $f(x)$ is a strictly increasing function then $\forall y,z \left[ y \lt z \Rightarrow f(y) \lt f(z)\right]$. In fact, this is the definition of strictly increasing function!
Prove that for function $f(x) = x^2 - x$, which notice is not strictly increasing, it is not true that $\forall y,z \left[ y \lt z \Rightarrow f(y) \lt f(z)\right]$.
To finish off our proof of the lower bound on the worst-case time for comparison-based sorting I asserted that there is a positive constant $c$ such that $\forall n \geq 4 \left[ \frac{n}{2} \lg n - \frac{n}{2} \geq c n \lg n \right].$ Prove this!