Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)

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]$.

Problem 1 (assessment: self_______ final_______)

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!