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.

  • 0
    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](http://en.wikipedia.org/wiki/Big_O_notation)2012-02-19
  • 0
    @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.2012-02-19
  • 1
    @UmNyobe The intersection would be around 26 if $\log_2$ where replaced with $\ln$, however.2012-02-19
  • 0
    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??2012-02-19
  • 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