Question about Asymptotic Notation

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.

• Hint: Instead of dividing by $2$, divide by $\log n$. The resulting inequality holds for $n$ sufficiently large. – Michael Burr Feb 28 at 9:37

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))$$.

• Would it be the case that you wouldn't be able to prove that f is asymptotically bounded below or above by g if you can't simplify one of the terms in the inequality to a constant? Since in both of your cases, you reduced one of the terms in the inequality to a constant. – ceno980 Feb 28 at 12:05
• No, it doesn't have to be the case that one side is reduced to a constant. What you need to do is to solve the inequality. For example, $$12\sqrt{n} \leq e^n$$ has a solution (around $3.041$, so for whole numbers rounded up $n\geq 4$). You don't even have to solve inequality in any precise manner. You just need to show that it holds for sufficiently large $n$. – Eff Feb 28 at 12:17