Comparing rates of growth with Big O

Question

This is a homework problem regarding comparing rates of growth for a Big O function.

a) $\log(n^2) = O(\log(n))$
b) $\log(n^2) = O(n)$
c) $\log(n^2) = O(n^2)$
d) All of the above

My inclination is to say that that A is incorrect and that B and C are correct, which wouldn't make sense. I don't really know how to go about solving this.

Answer 1

Recall \begin{align} \lim_{n\rightarrow \infty} f(n)= \mathcal{O}(g(n)) \end{align} if there exists $C>0$ such that \begin{align} |f(n)| \leq C g(n) \end{align} for all $n$.

a) Observe \begin{align} |\log(n^2)| = |2\log n| \leq 2 \log n \end{align} (Of course everything is equal, but I wanted to make a point).

b) Observe \begin{align} |\log(n^2)| = |2\log n| \leq 2 n. \end{align}

c) Observe \begin{align} |\log(n^2)|= |2\log n| \leq 2n^2 \end{align}

Answer 2

If you can find positive integers $M$ and $n_{0}$ such that $f(n) \le M g(n)$ for all $n \ge n_{0}$ then $f(n)$ is $O(g(n))$.

Answer is all of the above. You should be able to work out the answers directly using the definition above.