1
$\begingroup$

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

$\endgroup$
2
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.