1

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.

Ahmad Bazzi
  • 12,076
ceno980
  • 469

1 Answers1

0

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

Eff
  • 12,989
  • 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 '19 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 '19 at 12:17