Name: ____________________________________________________ Alpha: _____________________

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 1 (assessment: self_______ final_______)

Consider linearSearch and binarySearch from the Unit 1 notes. The analysis in Section 8 shows that the worst case running time in terms of number of operations for linearSearch on an array range of size $n$ is $T_{ls,\text{worst}}(n) = 2n + 1 \text{ operations}$ and the the worst case running time in terms of number of operations for binarySearch on an array of size $n$ is $T_{bs,\text{worst}}(n) = 5 \lg n + 4 \text{ operations}$ whereas the best case for each is $T_{ls,\text{best}}(n) = 3 \text{ operations}$ for linearSearch and $T_{bs,\text{best}}(n) = 5 \lg n + 4 \text{ operations}$ for binarySearch. Given that, here are some T/F questions to see whether you understand the meanings of $O$, $\Theta$ and $\Omega$ and how they're used to describe running time functions:
1. $T_{ls,\text{worst}}(n) \in \Theta(n)$
2. $T_{ls,\text{worst}}(n) \in \Omega(1)$
3. $T_{bs,\text{worst}}(n) \in O(n)$
4. $T_{bs,\text{worst}}(n) \in \Omega(\lg n)$
5. $T_{ls,\text{best}}(n) \in \Omega(n)$
6. $T_{ls,\text{best}}(n) \in \Theta(1)$
7. $T_{ls,\text{best}}(n) \in O(n)$
8. $T_{bs,\text{best}}(n) \in \Omega(n)$
9. $T_{bs,\text{best}}(n) \in O(\lg n)$
10. $T_{bs,\text{best}}(n) \in O(n)$

## Problem 2 (assessment: self_______ final_______)

Is $2^{n+1} \in O(2^n)$? Prove your answer! (Remember to look at the definition of Big-O and show that $2^{n+1} \in O(2^n)$ does/doesn't satisfy it.)

## Problem 3 (assessment: self_______ final_______)

1. 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.
2. 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.