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.

  • 1
    $\begingroup$ Hint: Instead of dividing by $2$, divide by $\log n$. The resulting inequality holds for $n$ sufficiently large. $\endgroup$ – 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))$.

  • $\begingroup$ 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. $\endgroup$ – ceno980 Feb 28 at 12:05
  • $\begingroup$ 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$. $\endgroup$ – Eff Feb 28 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.