How would you compare $O((\log n)^k)$ in relation to $O(n^c)$?

Question

How would you compare $O((\log n)^k)$ in relation to $O(n^c)$, $n,c \in \mathbb{N}*$ ? I'm very stuck on how to go about this.

I specifically need to see how $O((\log n)^{2021})$ relates to $O(n^3)$ and $O(\log n \cdot n^2)$. Thanks for any help I'm really stumped on this one. I tried using l'hôpital or proof by induction but I'm heading nowhere.

Answer 1

You have found

• $\log(\log n) = o(\log n)\qquad$

• i.e. $\log n$ grows faster than $\log(\log n)$ at least for large enough $n$

• and so $2021 \log(\log n) = o(3 \log n)$

• and from this $(\log n)^{2021} = o(n^3)$.

But large enough $n$ can require a big number.

That $2021$ makes a substantial difference, with $(\log n)^{2021} > n^3$ for $n$ between $3$ and about $2.75 \times 10^{2537}$.

For very large $n$, here from about $2.76 \times 10^{2537}$, $n^3> (\log n)^{2021}$ and increasingly so for larger $n$.

Answer 2

Here is an explicit bound showing that $\dfrac{(\ln(1+x))^k}{x^{c}} \to 0$ as $x \to \infty$.

For $x > 0, c>0$

$\begin{array}\\ \ln(1+x) &=\int_1^{1+x} \dfrac{dt}{t}\\ &=\int_0^{x} \dfrac{dt}{1+t}\\ &\lt\int_0^{x} \dfrac{dt}{(1+t)^{1-c}}\\ &=\int_0^{x} (1+t)^{c-1}dt\\ &=\dfrac{(1+t)^c}{c}|_0^{x}\\ &=\dfrac{(1+x)^c-1}{c}\\ &\lt\dfrac{(1+x)^c}{c}\\ &\text{so, replacing }c \text{ by } c/2\\ \ln(1+x) &\lt\dfrac{(1+x)^{c/2}}{c/2}\\ &\text{or}\\ \dfrac{\ln(1+x)}{x^c} &\lt\dfrac{2}{c(1+x)^{c/2}}\\ &\text{so that}\\ \dfrac{(\ln(1+x))^k}{x^{ck}} &\lt\dfrac{2^k}{c^k(1+x)^{ck/2}}\\ &\text{Replacing } c \text{ by } c/k\\ \dfrac{(\ln(1+x))^k}{x^{c}} &\lt\dfrac{2^k}{(c/k)^k(1+x)^{c/2}}\\ &=\dfrac{(2k/c)^k}{(1+x)^{c/2}}\\ \end{array} $