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) &lt;&lt; \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 &gt; \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 :)
L'Hôpital's rule shows that for $\epsilon &gt; 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 &gt; 0$.
This immediately implies that $\log^C n = o(n^\delta)$ for all $C,\delta &gt; 0$, taking $\epsilon = \delta/C$.