Does n^(1-1/d) always dominate log^d(n)

Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.

So I found out about k-d-trees with a query time of

$$\mathcal{O}(n^{1-\frac{1}{d}})$$

and range trees with a query time of

$$\mathcal{O}(\log^{d-1}n)$$

and would like to show that

$$\mathcal{O}(\log^{d-1}n) << \mathcal{O}(n^{1-\frac{1}{d}}) \quad \forall d \in \mathbf{N}$$

I tried around on Wolfram Alpha and the solutions were of the form

$$n > \exp\left(-d \cdot W_{-1}\left(\frac{-1}{d}\right)\right)$$

where $$W_k(z)$$ is the analytical continuation of the product log function. But I wasn't able to proof this always holds. Thank you in adnvance :)

1 Answer

L'Hôpital's rule shows that for $$\epsilon > 0$$, $$\lim_{n\to\infty} \frac{\log n}{n^\epsilon} = \lim_{n\to\infty} \frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}} = \lim_{n\to\infty} \frac{1}{\epsilon n^\epsilon} = 0.$$ In other words, $$\log n = o(n^\epsilon)$$ for all $$\epsilon > 0$$.

This immediately implies that $$\log^C n = o(n^\delta)$$ for all $$C,\delta > 0$$, taking $$\epsilon = \delta/C$$.