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 taking a course (algorithms) and the instructor assigns us problems from the CLRS Introduction to Algorithms 3rd edition. We aren't marked on the problems, they are just given as exercises.

Exercise 1.2-3 asks: at what value of n will an algorithm that runs at $100 n^2$ be faster than one that runs at $2^n$

Essentially I started out by arranging the question like so:

$100 n^2$ = $2^n$ and then I converted it to log format which gives: $n = lg\ 100 n^2$ as my limited math spidey senses told me if you are looking to find the value of an exponent, log is usually the way to do it.

But at this point I'm stuck, I'm not sure how to collect the n terms and get a meaningful answer to what n equals. Would I divide by $lg\ n^2$ on both sides? But if so, then what?

FYI: lg = $log_{2}$

share|improve this question

1 Answer 1

up vote 5 down vote accepted

This cannot be solved in closed form using elementary functions. Nor is that the point of the exercise. I suppose you should try some kind of binary serach starting from the observation that for instance $n=20$ suffices but $n=1$ does not.

share|improve this answer
1  
Once you are down to 20 (or even 2000) instances, I would just plug it into a spreadsheet and try them all instead of binary search. Copy down is your friend. –  Ross Millikan May 18 '11 at 3:11
    
Hrmph. Ok, it maddens me that this was the way I thought to solve it originally but shied away because I figured there must be something more they wanted. Exactly the type of question on an exam I'd waste a bunch of time on. Thanks for the prompt answer –  ThaDon May 18 '11 at 3:35
    
@ThaDon, I guess the point of the exercise is to give you a feeling of how those functions grow. After it, you should know that exponentials grow faster than polynomials, even if the polynomials have large leading coefficients. Moreover, it does not take at all long before an exponential overcomes a polynomial. –  lhf May 18 '11 at 11:35

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.