Menu

Class 2: Growth rates, asymptotic analysis


Reading
Sections 2.1 and 2.2 of Introduction to Algorithms.

Homework
  1. Determine graphically which of the following two functions has the higher asymptotic growth rate (or are they the same?):
    • f(n) = 3 n (sqrt(n)/n + log(n)) + 17 n + 10
    • g(n) = sqrt(n)*( 1 + log(n)*(1 + n))
    ... by plotting both using - for example - either Excel or Gnuplot (Gnuplot Info). Turn In: a screen capture of at least one of your plots, as well as a few sentences describing and justifying your conclusion about the asymptotic growth rate. Describe how you could have arrived at the same conclusion analytically instead of graphically.
  2. The growth rate for the average running time functions for both quicksort and heapsort is n lg n. However, most people will tell you that quicksort is usually faster. Explain this apparent contradiction.
  3. Heapsort's worst and average case running time functions both have n lg n growth rates. Insertionsort's worst and average case running time functions both have n2 growth rates. However, if you implement both algorithms and test them on an array of 10 randomly generated integers, you'll find that insertionsort is always faster. Explain this apparent contradiction.

From last class we learned ...
From last class we learned that characterizing "the running time" of an algorithm really requires us to provide functions giving the worst-case running time as a function of input size, the best-case running time as a function of input size, and the average-case running time as a function of input size.

What does "time" really tell you?
Okay, so suppose I give you the empirically observed worst case running time functions for implementations of two different sorting algorithms, algorithm A and algorithm B, for inputs of size up to some bound, and you discover that the value for A is less than the value for B for every input size. Is A's worst case running time better than B's? Hopefully you'd say "not necessarily"! Why is this one test not enough to tell which algorithm is better? Here are some possible problems:

  1. Were these test run on the same computer?
  2. Were these test programs written in the same language?
  3. Were both written by equally competent programmers?
  4. Were both written with equal care and attention?
  5. How do you know that the trial inputs you used actually included the worst cases for either algorithm?
  6. How do you know that B wouldn't be faster for input sizes beyond the bound you did your experiments up to?

All of these factors can affect the running time. So even having functions that give the time required by the algorithm as a function of input size doesn't really capture the idea of "running time" for the algorithm itself - only of one particular implementation, by one particular programmer, running on one particular machine, for one particular range of input sizes, and one particular sample of possible inputs!

What is analyzing algorithms all about? Part II
We know from the last class we know that we want to describe "running time" of an algorithm by describing the best-case, worst-case, and average-case time required by the algorithm as functions of input size. Some of the limitations of determining these functions experimentally were discussed in the previous section. To them, I'll add two very important limitations:

  1. To discuss and reason about running times, we would really like best/worst/average-case time functions to be given as nice formulas like "x^2" rather than big tables or plots of numerical data.
  2. We'd like to arrive at these expressions analytically, i.e. by reasoning about the algorithms, rather than experimentally. After all, implementing a sophisticated algorithm can require weeks or months of work. We'd rather know something about the performance of an algorithm before we invest all that time and energy.

So, we decided that the actual time required by an algorithm in seconds is less meaningful than you might think, and we decided that the ability to arrive at running-time descriptions analytically is really important. It's not really practical (or in any obvious sense meaningful) to arrive at a best/worst/average case running time in seconds for an algorithm analytically. In the face of this practical barrier, we need to lower our sights a bit and ask the following question: What can we determine analytically about an algorithm's best/worst/average case running time? We're going to lower our sights to something with less information, but still with enough information to be useful; something that's enough easier to determine as to be doable in practice.

What we often can do in practice, it turns out, is determine how an algorithm's best/worst/average case running times grow as the input grows. What we'll see, hopefully, is that this information - the growth rate of the best/worst/average case running time functions - actually tells you a whole bunch about the algorithm's performance! To understand why, you have to know a bit about growth rates and what's called asymptotic analysis.

NOTE: Eminent computer scientist Donald Knuth takes a different approach in his seminal series of books, "The Art of Computer Programming" ... at least for many familiar algorithms. He proposes a simple assembly language called MIX (soon to be superceded by MMIX). He implements basic algorithms (like BubbleSort) in MIX, and actually derives the exact worst-case (or best or average) number of MIX instructions executed. For example, his implementation of BubbleSort running on an array of N integers takes 7.5*N^2 + 0.5*N + 1 MIX instructions in the worst case. Let's just say that this kind of precisions is beyond most of our abilities ... especially when the algorithms get more complicated than BubbleSort!
Asymptotic analysis
The asymptotic behaviour of a function is what it does for very large inputs. If you compare two sufficiently "nice" functions asymptotically (and all our functions are nice), you need to look at input values that are large enough so that the relationship between the functions is constant.

We considered functions f(x) = n^2, g(x) = 3 n^2 - 10 n + 9. The graph of both functions together looks just the same for range n=1..1000 as the range n=1..2000, or for any larger range.

When the combined graph doesn't change for larger and larger ranges, we're seeing the asymptotic behaviour of the two functions. What this graph shows is that no matter how large the range, f is always about 1/3 of g.

When two functions differ asymptotically by no more than a positive constant multiple, we say that they have the same growth rate.

Let's now look at two functions that don't have the same growth rates. Consider f(x) = n^3 g(x) = 3 n^2 + 10 n + 9. The graph of both functions together looks just the same for range n=1..2000 as the range n=1..3000, or for any larger range.

When the combined graph doesn't change for larger and larger ranges, we're seeing the asymptotic behaviour of the two functions. What this graph shows is that, asymptotically, g is indistinguishable from zero relative to f. Thus, f and g do not have the same growth rate.

When function g is asymptotically indistinguishable from zero relative to function f we say that f has a greater growth rate than g.

Often you can't compare two functions and say that one is greater than the other. The first may be greater in one range, while the second is greater in another range. This is true even for simple functions like n and n*lg(n). However, for relatively nicely behaved functions, we can compare their asymptotic growth rates. The disadvantages are 1) that it doesn't tell you anything about small input values, and 2) that it can't distinguish between functions that differ asymptotically by no more than a positive constant multiple.

Growth rates
We look at some common, straightforward functions of n like sqrt(n), n^2, 2^n, etc, and we see that they grow at vastly different rates as n increases. They form a hierarchy, where each function in the hierarchy grows so much faster than the functions below it in the hierarchy that they all look like zero by comparison. So any function that grows like n^2, for example, will ultimately overtake any function that grows like sqrt(n), for example. Thus, if you compare the running times for two algorithms, the one with the slower growth rate is the superior algorithm ... as long as the input gets big enough.

So analyzing the growth rates of best/worst/average case running times (which is referred to as asymptotic analysis) is a compromise: On the plus side, figuring out growth rates analytically is so much easier than figuring out the actual functions that it is practical. On the minus side, you lose information about what happens when inputs are small, and you won't be able to distinguish two functions with the same growth rate.

For example, the average case running time for insertion sort grows like n^2 (where n is the number of elements to be sorted), whereas the average case running time for quick sort grows like n*lg(n). Based on asymptotic analysis all that we know is that quick sort's average case performance is much better than insertion sort for large arrays. What we've lost is the information that our experimental analysis from last class gave us, namely that for small arrays insertion sort is actually better.

For another example, the average case running time of heapsort grows like n*lg(n), where n is the number of elements to be sorted. How does it compare to quicksort? We don't know! Asymptotic analysis doesn't allow us enough information to determine that. Our notation for "f(n) grows like g(n)" is f(n) = Θ(g(n)). So when you see something like T(n) = Θ(n^2), that means that the function T(N) grows like n^2 grows. Of course "grows like" is something we'll define more precisely a bit later.

Reminder of definitions
There are a few terms that need reminding to make sure you can talk the talk concerning algorithm analysis.


Christopher W Brown
Last modified: Wed Jan 9 11:52:55 EST 2008