Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Asymptotic Analysis of Algorithms

The previous chapter presents a detailed model of the computer which involves a number of different timing parameters-- tex2html_wrap_inline57411, tex2html_wrap_inline57413, tex2html_wrap_inline57423, tex2html_wrap_inline57425, tex2html_wrap_inline57427, tex2html_wrap_inline57429, tex2html_wrap_inline57431, tex2html_wrap_inline57435, tex2html_wrap_inline57437, tex2html_wrap_inline57807, and tex2html_wrap_inline57471. We show that keeping track of the details is messy and tiresome. So we simplify the model by measuring time in clock cycles, and by assuming that each of the parameters is equal to one cycle. Nevertheless, keeping track of and carefully counting all the cycles is still a tedious task.

In this chapter we introduce the notion of asymptotic bounds, principally big oh, and examine the properties of such bounds. As it turns out, the rules for computing and manipulating big oh expressions greatly simplify the analysis of the running time of a program when all we are interested in is its asymptotic behavior.

For example, consider the analysis of the running time of Program gif, which is just Program gif again, an algorithm to evaluate a polynomial using Horner's rule.

   program1930
Program: Program gif again.

 

 

statement detailed model simple big oh
model
5 tex2html_wrap_inline57473 5 O(1)
6a tex2html_wrap_inline57489 4 O(1)
6b tex2html_wrap_inline57453 3n+3 O(n)
6c tex2html_wrap_inline57493 4n O(n)
7 tex2html_wrap_inline57495 9n O(n)
8 tex2html_wrap_inline57459 2 O(1)
TOTAL tex2html_wrap_inline59471 16n+14 O(n)
tex2html_wrap_inline59477
tex2html_wrap_inline57501
Table: Computing the running time of Program gif.

Table gif shows the running time analysis of Program gif done in three ways--a detailed analysis, a simplified analysis, and an asymptotic analysis. In particular, note that all three methods of analysis are in agreement: Lines 5, 6a, and 8 execute in a constant amount of time; 6b, 6c, and 7 execute in an amount of time which is proportional to n, plus a constant.

The most important observation to make is that, regardless of what the actual constants are, the asymptotic analysis always produces the same answer! Since the result does not depend upon the values of the constants, the asymptotic bound tells us something fundamental about the running time of the algorithm. And this fundamental result does not depend upon the characteristics of the computer and compiler actually used to execute the program!

Of course, you don't get something for nothing. While the asymptotic analysis may be significantly easier to do, all that we get is an upper bound on the running time of the algorithm. In particular, we know nothing about the actual running time of a particular program. (Recall Fallacies gif and gif).




next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.