Some Problems

Some of these exercises are mathematically demanding. I suggest that to those who find this difficult, that rather than becoming discouraged, skip over the questions straight to the further reading section. These exercises are somewhat more interesting for those who are interested in mathematical analysis.

1. Prove that $f(n) = 34 n^5 + 23n^3 + 3n^2 + 1$ is $o(n^7)$.
2. Prove that $f(n) = 2^n$ is $O(e^n)$ (Hint: use L'Hôpital's Rule).
3. Prove that $f(n) = \log(n)$ is $O(n)$ (Hint: Use L'Hôpital's Rule).
4. Prove if $f \in O(\alpha_1(n))$ and $g \in O(\alpha_2(n))$, then $(f + g) \in O(\alpha_1(n) + \alpha_2(n))$ (Hint: Consider the definition of big-O and the definition of limits!)
5. Prove if $f \in O(\alpha_1(n))$ and $g \in O(\alpha_2(n))$, then $(f + g) \in O(\max\left\{\alpha_1(n), \alpha_2(n)\right\})$. (Harder).
6. Prove if $f \in O(\alpha_1(n)$ and $g \in O(\alpha_2(n))$, then $(fg) \in O(\alpha_1(n)\alpha_2(n))$.
7. Prove that if $f \in O(\alpha_1(n))$ and $g \in O(\alpha_2(n))$, then there exists a $\eta \in \mathbb{R}$ such that $f \circ g \in O(\alpha_1(\eta\alpha_2(n)))$.
   (Hint: Use the following result: Let $f,g:\mathbb{R}\to \mathbb{R}$. Suppose there exists an $X_0$ such that $x \geq X_0$ implies $f(x) \leq g(x)$. Let $\Psi: \mathbb{R}\to \mathbb{R}$ such that as $x\to\infty$, $\Psi(x) \to \infty$. Then there exists an $X$ such that for all $x \geq X$ implies $\Psi \circ f (x) \leq \Psi \circ g (x)$. Try to prove this proposition, it's fun!)
8. Prove that in general if $f \in O(\alpha_1(n))$ and $g \in O(\alpha_2(n))$ implies $f \circ g \in O(\alpha_1 \circ \alpha_2(n))$ is not true.