FF2F334F-D8DC-48B1-B73C-185CC7BF416E.jpeg

  1. 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.
    1. $f(n)+g(n)=O(\text{max}(f(n), g(n))$)
    2. $f^2(n)=\Omega(f(n))$
    3. $f(n)+o(f(n))=\Theta(f(n))$, where $o(f(n))$ means any function $g(n)\in o(f(n))$.
    4. $f(n)=O(g(n))$ implies $2^{f(n)}=O(2^{g(n)})$