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'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?

share|improve this question
1  
WolframAlpha is handy for one off things like this. Here is a plot including the intersection. –  lewellen Jan 29 '13 at 22:25
    
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. –  viakondratiuk Jan 30 '13 at 6:02

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
Intersection if this 2 graphics gave me the point 6.5. So, my number is 6. Do you think your results correct? –  viakondratiuk Jan 30 '13 at 5:58
    
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$. –  Robert Israel Jan 30 '13 at 6:57
    
Thank you for your answer. –  viakondratiuk Jan 30 '13 at 7: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.