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

Question

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 :)

Answer 1

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