Quiz 2

The second quiz will focus on everything since the first quiz, so functions, pigeon hole principle, proofs by induction and recursively defined structures, big O, and worst-case runtime analysis, including analyzing recursive functions.

The quiz will have four questions. All will be worth 20, except the drill-style questions, which will be worth 40.

1. Write a simple proof that $f(n)=O(g(n))$ for a given $f(n)$ and $g(n)$.
2. Write a simple proof using mathematical induction.
3. Answer some drill-style questions. Many of these will in fact be questions from the drills.
4. Given some psuedocode, give a function expressing the number of primitive operations in terms of the input size, and give the “best” (i.e., tightest) big O bound on the function.