Elegant way to solve $n\log_2(n) \le 10^6$ I'm studying Tomas Cormen Algorithms book and solve tasks listed after each chapter.
I'm curious about task 1-1. that is right after Chapter #1.
The question is: what is the best way to solve: $n\lg(n) \le 10^6$, $n \in \mathbb Z$, $\lg(n) = \log_2(n)$; ?
The simplest but longest one is substitution. Are there some elegant ways to solve this? Thank you!
Some explanations: $n$ - is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out nmax.

To solve for $n\log_2(n)=10^6$, we can use the Lambert-W function. A bit of manipulation yields
$$
\log(n)e^{\log(n)}=10^6\log(2)
$$
and the Lambert-W function, being the inverse of $xe^x$, says that
$$
\log(n)=\mathrm{W}\left(10^6\log(2)\right)
$$
or
$$
n=\exp\left(\mathrm{W}\left(10^6\log(2)\right)\right)
$$
on the positive reals, the Lambert-W function is monotonically increasing, so you can simply get the desired inequality.
Mathematica gives the result $62746.1264697$ for N[Exp[LambertW[10^6Log[2]]],12].
Therefore, the largest $n$ is $62746$.
