How to solve $n < 2^{n/8}$ for $n$? This is from an exercise (1.2.2) in introduction to algorithms that I'm working on privately.
To find at what point a $n \lg n$ function will run faster than a $n^2$ function I need to figure out for what value $n$
$8n^2 > 64n \lg n$
(with lg here being the binary log)
after some elementary simplification we get
$n > 8\lg n$
Playing around with properties of log I can further get this to
$n^8 < 2^n$
or
$n < 2^{n/8}$
While I'm sure it's something very elementary I've lost somewhere over the years, after checking out a few logarithm tutorials I'm just not finding how to get any further on this.
Any help with solving for $n$ would be appreciated.
 A: The Lambert $W$ function can be used to solve equations of the form $p^{ax+b} = cx+d.$  In fact, the Wikipedia page gives the solution to $n = 2^{n/8}$ to be
$$n = \frac{-8}{\ln 2} W\left(\frac{-\ln 2}{8}\right).$$
Via Mathematica, which implements the $W$ function as ProductLog, this comes out to be 43.5592 (although you have to take the lower branch of the $W$ function), in agreement with the Newton iteration solution Theo Buehler mentions.
A: It's not hard to show that $f(x) = x - 8 \lg x$ only has one critical point. Since $f(2) \lt 0$ it suffices to find $x \gt 2$ such that $f(x) > 0$.
Take $n = 2^{k}$ then you get $2^{k} > 8k$ from your second inequality and plugging in $k$ from $1$ on shows that $n = 2^6 = 64$ will do. You can check by hand that $n = 44$ is optimal, as $f(44) \gt 0 \gt f(43)$. 
A: Since it doesn't take long for $2^{n/8}$ to get larger than $n$, it would be reasonable to experiment to find roughly where this happens, using multiples of $8$ to make it easy.  E.g., $40\gt 2^5$, but $48<2^6$.  The smallest solution (not counting $n=1$) is thus somewhere between $41$ and $48$.  It is geometrically clear from the shape of the curves $y=x$ and $y=2^{x/8}$ that all greater $n$ will work, but to prove it you could use mathematical induction.  
Claim: If $n\geq 44$, then $n\lt 2^{n/8}$.
Proof: The base case is $n=44$, for which I'll omit the verification.  Suppose for some $n\geq 44$ that $n\lt 2^{n/8}$.  Then $2^{(n+1)/8}=2^{1/8}2^{n/8}\gt 2^{1/8}n$.  Since $n\geq 44$, $\frac{n+1}{n}=1+\frac{1}{n}\leq 1+\frac{1}{44}\lt 2^{1/8}$.  Thus $2^{1/8}n\gt n+1$, and combining with the previous inequality completes the inductive step.
I'll also omit the verification that $43\gt 2^{43/8}$.
