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