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

  • 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