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