I am doing a question on asymptotic notation. I have two functions $f(n)$ and $g(n)$, where $f(n) = (\log_2n)^2$ and $g(n) = \log_2n^{\log_2n} + 2\log_2n$. I have to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$.
My approach to figuring this out is to determine whether $g(n)$ grows faster than $f(n)$ or if $f(n)$ grows faster than $g(n)$. To do this, I am trying to prove whether $2\log_2n \leq (log_2n)^2$ for all $n \geq c$, where $c$ is a constant. I want to prove this because if it is true, then it can be said that $f(n)$ grows faster than $g(n)$ for all $n \geq c$ (where $c$ is a constant). I know that I would also have to prove whether $\log_2n^{\log_2n} \leq (log_2n)^2$ in order to say that $f(n)$ grows faster than $g(n)$ for all $n \geq c$.
So far I have:
$$ \log_2n \leq (log_2n)^2 $$
$$ 2\log_2n \leq 2(log_2n)^2 $$
However, I am not sure where to go from here in trying to prove whether $2\log_2n \leq (log_2n)^2$. Dividing both sides of the inequality by 2 will not achieve anything.
Am I taking the right approach for solving this question, or is there a better way to determine the asymptotic complexity of $f(n)$? Any insights are appreciated.
Best Answer
We have that $$f(n) = (\log_2 n)^2$$ and $$g(n) =\log_2 n^{\log_2 n} + 2\log_2 n = (\log_2 n)^2 + 2\log_2 n $$ This last equality is derived by using the logarithm law that $\log(a^b) = b\log(a)$.
Question 1. Is $f$ asymptotically bounded below by $g$? That is, does there exist an $N_1$ and a $k_1 > 0$ such that $$f(n)\geq k_1 \cdot g(n) $$
for all $n\geq N_1$?
Answer 1. We have that $$ (\log_2 n)^2 \geq k_1 \cdot \left((\log_2 n)^2 + 2\log_2 n\right)$$
Set $k_1 = 1/2$, then $$(\log_2 n)^2 \geq \frac12 (\log_2 n)^2 + \log_2 n $$
By subtracting $(1/2) (\log_2 n)^2$, we get $$\frac12 (\log_2 n)^2 \geq \log_2 n $$ Dividing by $\log_2 n$ we get $$\frac12 \log_2 n \geq 1 $$ which is true for all $n\geq 4 = N_1$. Hence, $f$ is asymptotically bounded below by $g$.
Question 2. Is $f$ asymptotically bounded above by $g$? That is, does there exist an $N_2$ and a $k_2 > 0$ such that $$f(n) \leq k_2\cdot g(n) $$ for all $n\geq N_2$?
Answer 2. We have that $$ (\log_2 n)^2 \leq k_2 \cdot \left((\log_2 n)^2 + 2\log_2 n\right)$$
Set $k_2 = 1$, then $$(\log_2 n)^2 \leq (\log_2 n)^2 + 2\log_2 n $$
Subtract $(\log_2 n)^2$, then $$0\leq 2\log_2 n $$ which is true for all $n\geq 1 = N_2$. Hence, $f$ is asymptotically bounded above by $g$.
Conclusion. We conclude that $f$ is both bounded below and above asymptotically by $g$. Specifically, to be more precise, this is true with constants $1/2$ and $1$ and for $N = \max(N_1,N_2) = 4$. This means that $$\frac12\cdot g(n) \leq f(n) \leq 1\cdot g(n) $$ for all $n\geq 4$.
In asymptotic notation, this means that $f(n)$ is $\Theta (g(n))$.