Tom Kelliher, CS23
Apr. 12, 1996
Algorithm analysis covers:
What determines running time?
How is it fair to compare two programs?
Should we compare?
What should we compare?
Why should we compare?
Idea: count something.
How many times does the inner loop body execute?
for (i = 0; i < n; ++i) for (j = 0; j < i; ++j) ; // inner loop body
Find closed forms for:
if constants c and exist such that for all .
A fallacious example: is O.
Typical growth rates (from slowest to fastest)
Why use a difficult, subtle, fast algorithm on small inputs?
What is the efficiency of
Implement mergesort (don't look in the textbook!).