Asymptotic Analysis of Cubed Root

Question

According to one of my textbooks, $\sqrt{n}$ is of higher order than $(\log{n})^2$. When I compare $\sqrt[3]{n}$ and $(\log{n})^3$ in my graphing calculator, though, it appears that $(\log{n})^3$ is of higher order than $\sqrt[3]{n}$. Is there a general conclusion I can draw about $\sqrt[k]{n}$ and $(\log{n})^k$ for $k \in \mathbb{N}$ (which one increases faster asymptotically)?

Answer 1

Alright, with more accuracy, the place where your two degree 3 items are equal is a real number between the consecutive integers $$ 25438034785804 \; \; \; , \; \; \; 25438034785805 $$ for the larger, we have $\log_e n \approx 30.867266602430960527909691312812151398 $ so that $(\log_e n )^3 \approx29409.965764690120213895623606447861451 $ And $ \sqrt[3] n \approx 29409.965764690231895945701392803872488 $

Answer 2

Using algebra, we have the explicit solution $$n^{\frac{1}{k}}=\log ^k(n)$$ Let $n=e^x$ and raise to power $k$ to make $$e^x=x^{k^2}\qquad \implies \qquad x=-k^2\,\, W_{-1}\left(-\frac{1}{k^2}\right)$$ $$n=\exp\left(-k^2\,\, W_{-1}\left(-\frac{1}{k^2}\right) \right)$$ that you could round the way you want.

If you cannot use Lambert function, you can use the bounds given by Chatzigeorgiou in $2013$

$$-1-\sqrt{2u} -u < W_{-1}\left(-e^{-u-1}\right)<-1-\sqrt{2u} -\frac 23u $$ Using $u=2\log(k)-1 $ gives $$\frac{1}{3} k^2 \left(4 \log (k)+3 \sqrt{4 \log (k)-2}+1\right) < x <k^2 \left(2 \log (k)+\sqrt{4 \log (k)-2}\right)$$ Start with $x_0$ at the midpoint and make one iteration of Newton method o get $$x_1=x_0-\frac{x_0 \left(x_0-k^2 \log (x_0)\right)}{x_0-k^2}$$

Trying for $k=3$ gives $$30.1100 < x <33.7016\qquad \implies \qquad x_0=31.9058\qquad \implies \qquad x_1=30.8741$$ while the exact solution is $x=30.8673$.

Now, a binary search for $n$ will be quite fast.

Answer 3

Let $a(n)=n^{1/k}$, $b(n)= \log(n)^k$

Then, let $La(n) = \log a(n) = \frac{1}{k} \log n$, and $Lb(n)= k \log \log n$

Then, $La(n)$ is of higher order, and so is $a(n)$, for any $k$.