Finding whether $f(n)$ is $O$, $o$, $\Omega$, $\omega$ or $\Theta$ of $g(n)$.

Question

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

Log is assumed to be base 2.

Now I put this in the as $f(n)/g(n)$ which is of the form $\frac \infty{\infty}$. So then I applied L'hopital's rule giving me

$f(n) = 1 \ + \ 2 log(n) \frac1{n(ln(2))}$

$g(n) = 1 + 2\ \frac1{n(ln(2))}$ now if I do $f(n)/g(n)$ I get

$\frac {1 \ + \ 2 log(n) \frac1{n(ln(2))}} { 1 + 2\frac1{n(ln(2))}}$

Now since the $\frac1{n(ln(2))}$ part in both equations tends to 0, I'm left with 1/1 and thus $f(n) = \Theta g(n)$

Is this correct?

Answer 1

Yes. We can also use another approach, without the heavy artillery of L'H\^opital's Rule: $$ {f(n) \over g(n)} = {n + (\log n)^2 \over n + \log (n^2)} = {n + (\log n)^2 \over n + 2 \log n} = {n \; (1 + (\log n)^2/n) \over n \; (1 + 2 (\log n) /n)} = {1 + (\log n)^2/n \over 1 + 2 (\log n) /n}. $$ We see that, as $n \rightarrow \infty$, both the numerator and denominator tend to $1$.

Answer 2

Of course, more than one of those relations can hold. Let's consider them one at a time, all under the assumption that the discussion is about large $n$ asymptotics.

$f(n) = \mbox{O} (g(n))$ for large $n$ if there is some $n_0$ and a constant $C$ such that for all $n>n_0$, $$ |f(n)| \leq C|g(n))| $$ Since $f(n) = n+(\log n) \log n$ and $g(n) = n+2\log n$, we can take $n_0 = 10$ and $C = 2$ to show that this definition is met: $$ n > 10 \implies n > (\log n) \log n \implies (\log n) \log n < \frac n{\log n}\\ n + (\log n) \log n < n + \frac n{\log n} \log n = \frac n2+ \left( \frac{n}{2\log n}+ \frac n{\log n}\right)\log n < \frac n2+ 2\log n $$

$f(n) = \mbox{o} (g(n))$ for large $n$ if for any fixed positive $\epsilon$ there is some $n_0$ (which may depend on $\epsilon$ there is some $n_0$ and a constant $C$ such that for all $n>n_0$, $$ |f(n)| \leq \epsilon|g(n))| $$ Since $$\frac{|f(n)|}{|g(n)|} = 1 + \frac{(n-2)\log n}{n+2\log n}$$ and $g(n) = n+2\log n >1$ for $n>2$, testing against any $\epsilon <1$ reveals that $f(n)$ is not $\mbox{o}(g(n))$.

You can also, in this way, show that $g(n)$ is not $\mbox{o}(f(n))$

$f(n) = \Omega (g(n))$ for large $n$ if there is some $n_0$ and a constant $C >0$ such that for all $n>n_0$, $$ |f(n)| \geq C|g(n))| $$ (That is, $f(n) = \Omega (g(n))$ if and only if $g(n) = \mbox{O}f(n)$.) Take $C = \frac12$ and $n_0 = 10$; then to show $g(n) = \mbox{O}f(n)$ it suffices to show that when $n > 10$ $$ n + (\log n) \log n < 2 n + 4\log n $$ Show this by noting that the derivative of $$ 2n + 4 \log n = n + \left(\frac{n}{\log n}+4\right) \log n > n + \left(\frac{n}{\log n}\right) \log n > n + (\log n) \log n $$

Finally, since the big O applies in both directions, $f(n) = \Theta(g(n))$.