# minimizing the maximum between a degree of a tree and its height

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