# How can I solve $8n^2 = 64n\,\log_2(n)$

I currently try to analyze the runtime behaviour of several algorithms. However, I want to know for which integral values $n$ the first algorithm is better ($f(n)$ is smaller) and for which the second one is better.

The two algorithms:

$$f(n) = 8n^2$$

$$g(n) = 64n\,\log_2(n)$$

I started by equaling the two to $8n^2 = 64n\,\log_2(n)$. The problem is that $n$ is both outside and inside a $\log_2$, and I don't know how to resolve this.

-
Don't try these because it is useless on real problems. In your case it intersect around 26. This is Complexity analysis (probably better on Stackoverflow). Read Big O on wiki –  UmNyobe Feb 19 '12 at 9:28
@UmNyobe Why do you say "it is useless on real problems"? Both these algorithms have polynomial runtimes, of low degree in fact, which is pretty good. As a side note, the two intersections are around 1 and 43, rather than 26. –  Alex Becker Feb 19 '12 at 9:34
@UmNyobe The intersection would be around 26 if $\log_2$ where replaced with $\ln$, however. –  Alex Becker Feb 19 '12 at 9:35
sorry I forgot to divide by log(2). What I mean is n^2 will be better than nlog(n) on inputs where the speed improvement is not noticeable, while nlog(n) will drastically be better as n grows. Of course you can take the example of n^2 versus 100000nlog(n), but how are you going to have those two complexities for a real program?? –  UmNyobe Feb 19 '12 at 9:40

You could try to solve this using the Lambert W function but it is probably easier to do it numerically and find that (for integers) $f(n) \lt g(n)$ when $2 \le n \le 43$.

For $n \ge 44$ (and $n=1$) you have $f(n) \gt g(n)$.

-

$64 n \cdot \log_{2} n-8n^2=0 \Rightarrow 8n \cdot (8\log_{2} n-n)=0$ , hence :

$~ 8\log_{2} n-n=0~$ since $~n~$ cannot be $~0~$ , so:

$8\log_{2} n=n \Rightarrow \log_{2} n= \frac{1}{8} \cdot n\Rightarrow 2^{\frac{1}{8}n}=n$

Substitute : $\frac{1}{8}n=t~$, so :

$$2^t=8t \Rightarrow 1=\frac{8t}{2^t} \Rightarrow 1 = 8t \cdot e^{-t \ln 2} \Rightarrow \frac{1}{8}=t\cdot e^{-t \ln 2} \Rightarrow$$

$$\Rightarrow \frac{-\ln 2}{8}=(-t\cdot \ln 2)\cdot e^{-t \ln 2} \Rightarrow$$

$$\Rightarrow W\left(\frac{-\ln 2}{8}\right)=-t \ln 2 \Rightarrow t = \frac{-W\left(\frac{-\ln 2}{8}\right)}{\ln 2} \Rightarrow$$

$$\Rightarrow n= -8 \cdot \frac{W\left(\frac{-\ln 2}{8}\right)}{\ln 2}$$

where $W$ is a Lambert W function .

-

I assume you are only interested in positive values of $n$. The equation $8n^2 = 64n\log_2(n)$ can be simplified to $n=8\log_2(n)$. WolframAlpha approximates the two solutions to this equation as $n=1.1$ and $n=43.5593$, and in between these two we have $8n^2 < 64n\log_2(n)$ while otherwise $8n^2 > 64n\log_2(n)$. Thus for $43\geq n\geq 2$ we have that $g(n)>f(n)$, while otherwise $g(n)<f(n)$.

-
@Henry Of Course, thanks. –  Alex Becker Feb 19 '12 at 9:51
+1 Do you mean to say that this is best solved by substituting integers into the inequality, and examining the result. Is there a more algorithmic way to solve this type of problem? I imagine myself wasting a lot of time punching in random numbers trying to find the ones that work! –  trideceth12 Mar 8 '13 at 15:22