
- Determine whether the following statements are true. If true, provide a proof; otherwise, provide a counterexample.
Assume that $f(n)$ and $g(n)$ are asymptotically positive functions.
- $f(n)+g(n)=O(\text{max}(f(n), g(n))$)
- $f^2(n)=\Omega(f(n))$
- $f(n)+o(f(n))=\Theta(f(n))$, where $o(f(n))$ means any function $g(n)\in o(f(n))$.
- $f(n)=O(g(n))$ implies $2^{f(n)}=O(2^{g(n)})$