300 CHAPTER 5 Analysis of Algorithms
The purely theoretical approach introduced here makes an approximation of the com-
plexity to an algorithm that ignores almost all differences among machines, languages,
and details of how the algorithm is coded. If functions T 1 (n) and T 2 (n) measure the times
taken by programs 1 and 2 on a data set of size n, then this approach asks only whether
T1 c O(T 2 ) and whether T 2 E O(TI). This approach is said to measure only time com-
plexity, not time in all its detail. Despite being highly theoretical, this approach has very
frequently proved to be an excellent guide for practical decisions. For example, it allows
one to conclude that a sorting algorithm that is in 0(n^2 ) is clearly inferior to a sorting
algorithm that is in O(n ln(n)). For the standard sorting algorithms, unless you are sorting
a very short list (of fewer than eight elements or so) or a list that is already almost in order,
an algorithm in 0(n ln(n)) is decidedly preferable.
There are many variations on the way to measure complexity. Different approaches
may work with different idealized models of what a computer is or of what is to be mea-
sured. What we do here is typical of most current discussions of complexity. At the end
of this section, we will discuss briefly some common variants of the notion of algorithm
complexity.5.3.1 Counting Statements
To illustrate how to measure an algorithm's complexity, we start with some very simple
algorithms. The following algorithm tests whether a list of three numbers is in increasing
order:INPUT: Values for three variables A, B, and C
OUTPUT: Message indicating whether A < B < C is TRUEif (A < B and B < C) then
print "List is in order."
else
print "List is out of order."Typically, you pick a single operation, or a small set of operations, called key opera-
tions, to analyze algorithms. You then count, for inputs of various size, how many times
these key operations are performed when an algorithm is executed. In the algorithm just
cited, we would count the number of comparisons made between elements of the list. In
this case, two comparisons obviously are made, no matter what the input list is. However,
counting statements executed just by looking at the program and its input often is not this
easy. Therefore, we illustrate here some simple techniques for doing this.
One of the basic tenets of structured programming is that all programs should be
built from just a few, simple, well-understood control structures. Although object-oriented