Prove whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$. $f(n) = n + (\log n)^{2}$, $g(n) = n + \log(n^{2})$.

Question

$f(n) = n + (\log n)^{2} , g(n) = n + \log(n^{2} ).$

Now so far I've done $g(n) = n+ 2\log(n)$

and then I think since its the same change to both, I can remove $n$.

leaving me with $f(n) = (\log n)^{2}$ and $g(n) = 2\log(n)$ now if I do $f(n)/g(n)$ I get

$((\log n)^{2}) / (2\log n)$

and since the numerator is growing exponentially and the bottom is growing linearly? As we approach positive infinity the function approaches positive infinity. Thus $f(n)$ is $\omega$ of $g(n)$?

I don't know if this proof is done right, if its what is a better alternative? I am still new to this and learning!

Answer 1

$\frac {f(n)} {g(n)}=\frac {n+(\log\, n)^{2}}{ n+2\log\, n}=\frac {1+(\log\, n)^{2}/n} { 1+2(\log\, n)/n} \to 1$

Answer 2

You're pretty much done with $O$ by doing the $g(n) = n+ 2\log(n)$ transformation, since $$f(n) = n + (\log n)^{2} \\ g(n) = n + 2 \log(n)$$ Assuming that $\log$ means $\ln$: $$\forall n \ge 8 \quad f(n) > g(n)$$ Since $\ln(8) > 2$, and $ln$ is monotone increasing.

This means that $g(n) = O(f(n))$.