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.

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.

- $T_{ls,\text{worst}}(n) \in \Theta(n)$
- $T_{ls,\text{worst}}(n) \in \Omega(1)$
- $T_{bs,\text{worst}}(n) \in O(n)$
- $T_{bs,\text{worst}}(n) \in \Omega(\lg n)$
- $T_{ls,\text{best}}(n) \in \Omega(n)$
- $T_{ls,\text{best}}(n) \in \Theta(1)$
- $T_{ls,\text{best}}(n) \in O(n)$
- $T_{bs,\text{best}}(n) \in \Omega(n)$
- $T_{bs,\text{best}}(n) \in O(\lg n)$
- $T_{bs,\text{best}}(n) \in O(n)$

- The average-case running time functions for both quicksort and heapsort are $\Theta(n \lg n)$. However, most people will tell you that quicksort is usually faster. Explain this apparent contradiction.
- Heapsort's worst and average case running time functions are both $\Theta(n \lg n)$. Insertionsort's worst and average case running time functions are both $\Theta(n^2)$. However, if you implement both algorithms and test them on an array of 10 randomly generated integers, you'll find that insertionsort is always faster. Explain this apparent contradiction.