1
$\begingroup$

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

1 Answers 1

5

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.

  • 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.2011-05-18
  • 0
    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 answer2011-05-18
  • 0
    @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.2011-05-18