Problem 0: Complete the two Canvas quizzes in "PSet 12 - Asymptotic Notation and Linear Algebra".

Problem (15 points): Prove each of the following statements using the definitions of $O$ and $\Theta$.

• Prove that $2n^2 + 30n + 6 \in \Theta(n^2)$.
• Prove that $n! \in O((n+1)!)$.
• Prove that $(n+1)! \not\in O(n!)$.

Problem (10 points): Suppose a function $f:\mathbb{Z}^+ \rightarrow \mathbb{R^+}$ is defined by $$f(n) = \begin{cases} g(n), & \text{if }n\text{ is even} \\ h(n), & \text{if }n\text{ is odd} \end{cases} $$ where $g, h:\mathbb{Z}^+ \rightarrow \mathbb{R^+}$.

• Prove that $f(n) \in O((g + h)(n))$ ($g+h:\mathbb{Z}^+ \rightarrow \mathbb{R^+}$ is defined by $(g+h)(n) = g(n) + h(n)$).
• Prove that, if additionally $h(n) \in \Theta(g(n))$, then $f(n) \in \Theta((g + h)(n))$.

---