Is this Asymptotic Statement true?

179 Views Asked by At

Is this statement true? If so, how can I prove it? If not, why not? $$ \frac{n^2}{\log{(n)}} \in \Theta(n^2) $$

Recall the definition of Big Theta asymptotic notation: $f(n) \in \Theta(g(n))$ means that there exist constants $k_1$ and $k_2$ such that for all sufficiently large $n$, we have, $$ k_1g(n) \leq f(n) \leq k_2g(n).$$ "Sufficiently large" means that there exists a constant $N$ (depending on $k_1$ and $k_2$) such that the above inequalities hold for all $n > N$.

When plotting $f(n) = \frac{n^2}{\log{(n)}}$ (black curve) and $g(n) = n^2$ (red curve), I can see only $k_1$:

enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

Pick $N_0 = 8$, so $\log n \ge 3$ whenever $n \ge N_0$, then also $$ \frac{n^2}{\log n} \le \frac{1}{3} \cdot n^2 $$ This is one half. The other half won't work, there is no upper limit to $\log n$

In summary is $O(n^2)$, but not $\Omega(n^2)$, so it is not $\Theta(n^2)$.