2
$\begingroup$

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.

  • 2
    possible duplicate of [How to solve n < 2^{n/8} for $n$?](http://math.stackexchange.com/questions/20652/how-to-solve-n-2n-8-for-n)2015-09-29

3 Answers 3

5

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

3

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

1

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

  • 0
    +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!2013-03-08