I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically.

If I set $k = \frac {\log n}{\log \log n}$, then the height of the tree is $\log_\frac{\log n}{\log \log n}(n) = \frac{\log n}{\log \frac {\log n}{\log \log n}}$.

What is the asymptotic height of that tree, is $$\frac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\frac{\log n}{\log \log n})$$ and if so, is this optimal?


Yes, it is true that $\dfrac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\dfrac{\log n}{\log \log n}).$ In fact, we have the following more accurate approximation, $$\frac{\log n}{\log \frac {\log n}{\log \log n}} \sim \frac{\log n}{\log \log n}.\tag{app}$$

Proof. $$\begin{aligned} \lim_{n\to\infty}\frac{\ \frac{\log n}{\log \frac {\log n}{\log \log n}}\ }{\ \frac{\log n}{\log \log n}\ }&=\lim_{n\to\infty}\frac{\log\log n}{\log \frac {\log n}{\log \log n}} =\lim_{n\to\infty}\frac{\log\log n}{\log\log n-\log\log \log n}\\ &=\frac{1}{1-\lim_{n\to\infty}\frac{\log\log \log n}{\log\log n}} =\frac{1}{1-0}=1. \end{aligned}$$

So, if we set $k = \frac {\log n}{\log \log n}$, then the height of the tree, $\frac{\log n}{\log \frac {\log n}{\log \log n}}$ is $\frac{\log n}{\log \log n}$ asymptotically and, hence, so is the larger one between the height of the tree and $k$.

Now, the question is what is the asymptotic behavior of the minimum of the larger one between $\log_kn $ and $k$, i.e. $h(n)=\min_k\max(\log_kn,k)$.

Since $k$ is increasing with respect to $k$ while $\log_k n$ is decreasing with respect to $k$, the minimum of the larger one between $k$ and $\log_k n$ for a given $n$ is obtained when $k=\log_k n$, assuming $k,n>1$.

What is the solution to $k=\log_k n$ for a given $n$? $$k=\log_kn\Leftrightarrow k= \frac{\log n}{\log k}\Leftrightarrow \log k\cdot k= \log n\Leftrightarrow \log k\cdot e^{\log k}= \log n$$ By the definition of the Lambert $W$ function, we should have $$\log k = W_0(\log n),$$ where $W_0(\cdot)$ is the principal branch of the Lambert $W$ function, as we are only interested in the real positive values. So, $$k = e^{W_0(\log n)}.$$ Accordingly, $$h(n)=\left.\max(\log_kn,k)\right|_{k=e^{W_0(\log n)}}=e^{W_0(\log n)}.$$

The same article on Lambert $W$ function tells that $$ W_0(x) = \log x - \log\log x + o(1).$$ Substituting $\log n$ for $x$, we have $$ W_0(\log n) = \log\log n - \log\log\log n + o(1).$$ So, $$ h(n) =e^{W(\log n)}= e^{\log\log n} e^{-\log\log\log n} e^{ o(1)}=\frac{\log n}{\log\log n}\ e^{o(1)},$$ Since $e^{o(1)}$ goes to 1 when $n$ goes to infinity, $$h(n)\sim{\frac{\log n}{\log\log n}}.$$

Combining the above conclusions, we see that if we set $k = \frac {\log n}{\log \log n}$, then the larger one between the height of the tree and $k$ approaches its minimum $h(n)$ as well as ${\frac{\log n}{\log\log n}}$ asymptotically.

To be nit picky, it should be pointed out that we have been ignoring the expected requirement that $k$ should be an integer. It would require cumbersome analysis to adapt the above analysis and conclusion for integer $k$. In the end, we have still $$\min_{1\lt k\le n,\ k\in\mathbb N}\max(k, \log_kn)\sim\frac{\log n}{\log\log n}.$$


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.