1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ WolframAlpha is handy for one off things like this. Here is a plot including the intersection. $\endgroup$
    – GEL
    Jan 29 '13 at 22:25
  • $\begingroup$ When I opened that page first time, I saw plot for natural logarithm, but I switched to base 10 logarithm and get correct number. I think it's 6.5. $\endgroup$ Jan 30 '13 at 6:02
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Intersection if this 2 graphics gave me the point 6.5. So, my number is 6. Do you think your results correct? $\endgroup$ Jan 30 '13 at 5:58
  • $\begingroup$ Sorry, I had the impression it was supposed to be the base $2$ logarithm (which is commonly used when dealing with algorithms). Apparently you want base $10$, in which case the intersection is indeed at approximately $6.5$. $\endgroup$ Jan 30 '13 at 6:57
  • $\begingroup$ Thank you for your answer. $\endgroup$ Jan 30 '13 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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