Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.