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

• I changed the title to make it a more precise description of what you were asking. If you don't like it feel free to change it back. – Mike Spivey Feb 6 '11 at 22:43
• looks fine to me – juhanic Feb 15 '11 at 6:01

## 3 Answers

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

• That looks fine to me, and reminds me that I was trying to solve something outside the problem specification, namely the exact value of n where $2^n = n^8$. As a point of curiosity, can an exact number be calculated for that? – juhanic Feb 6 '11 at 5:45
• @juhanic: I don't think so, these transcendental equations are usually not solvable explicitly. With Newton iteration I find $n \approx 43.559$. – t.b. Feb 6 '11 at 5:50
• ok, well that certainly explains why I was puzzling over this for a long time. I was trying to solve the wrong problem. Thanks – juhanic Feb 6 '11 at 5:54

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

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.