How to find on what ranges one sorting algorithm is better than other?

Question

I'm reading the book "Introduction to algorithms" and want to solve one task from it. But don't know the best way how to find solution.

The task is:

We have 2 sorting algorithms. Сomplexity of first one is $8 n^2$, the second is $64 n \lg n$. I want to find the range of $n$ when first algorithm is better than second.

I understand different ways how to solve it:

1. I can take numbers one by one from range $[2..n]$ an find both values. According to them find a place when values of first algorithm become greater than second.

2. I understand that I can solve $8 n ^2$ < $64 n \lg n$. But have no idea how to do it. Maybe someone can assist with it or give a link where to read.

3. I can build graphics and find intersection point. But I had a problem with it. I don't want to build them on the paper. I found such online programm as Sage. But I can't find how to build graphic for logarithm. I'm trying:

   a=plot(8*n^2)

   b=plot(64*n*log(10, n), rgbcolor='red')

   (a+b).show()

   But it's not working. Maybe somebody can help with it? And what is the most popular programm for such mathematics tasks?

Answer 1

To get the graphics, put:

8*x**2, 64*x*log x

in google. You will get the graph of the two functions and "see" the interval requested.

Answer 2

In Maple 16:

solve(8*n^2<64*n*log[2](n));

$$\text {RealRange} \left( \text {Open} \left( -{\frac {8\; \text {LambertW} \left( -\frac{\ln \left( 2 \right)}{8} \right) }{\ln \left( 2 \right) } } \right) ,{\it Open} \left( -{\frac {8\;\text{ LambertW} \left( -1,- \frac{\ln \left( 2 \right)}{8} \right) }{\ln \left( 2 \right) }} \right) \right) $$

evalf(%);

$$ \text{RealRange}(\text{Open}(1.099997030),\text{Open}(43.55926044))$$

So for integers $n$ the answer is $2 \le n \le 43$.