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$


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

  • $\begingroup$ 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. $\endgroup$ – Mike Spivey Feb 6 '11 at 22:43
  • $\begingroup$ looks fine to me $\endgroup$ – juhanic Feb 15 '11 at 6:01

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

  • $\begingroup$ 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? $\endgroup$ – juhanic Feb 6 '11 at 5:45
  • $\begingroup$ @juhanic: I don't think so, these transcendental equations are usually not solvable explicitly. With Newton iteration I find $n \approx 43.559$. $\endgroup$ – t.b. Feb 6 '11 at 5:50
  • $\begingroup$ ok, well that certainly explains why I was puzzling over this for a long time. I was trying to solve the wrong problem. Thanks $\endgroup$ – 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.


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.