Section 3.3 Analysis of Algorithms
203
S e c t I o n 3 . 3 analysis of algoRithms
The General Idea
Often more than one algorithm can perform the same task. Because we assume that
all these algorithms perform correctly, we need some other basis of comparison to
decide which algorithm to use in a given situation. Several criteria could be used
to judge which is the “best” algorithm. We might ask, for example, which is easiest to understand, which makes the most efficient use of machine memory when
implemented as computer code, or which runs most efficiently. One might expect
that to judge whether an algorithm is “running efficiently” means standing by with
a stopwatch while the computer code executes. But the stopwatch approach may tell
us more about the speed of the processor than it does the inherent efficiency of the
algorithm. Even timing the code for competing algorithms on the same processor
and using the same input data can give a misleading picture of what might happen
when the input data set is larger.
Instead, we evaluate the time efficiency of an algorithm by estimating the
number of operations it must perform. We count only the operations that are
basic to the task at hand, not “housekeeping” operations that make just a small
contribution to the total work required.
The study of the efficiency of algorithms, that is, the number of operations
they perform, is called analysis of algorithms. Various techniques for algorithm
analysis have been developed. Sometimes a rather straightforward analysis can be
done simply by inspecting the algorithm.
example 27
Following is an algorithm to write out, for each student on a grade roster, the sum
of m quiz grades minus the lowest grade. The outer loop goes through each of the
n students; the inner loop goes through the quizzes for the current student. For each
student, the successive quiz grades are added and the lowest grade is ultimately
subtracted from the sum of all the grades. These additions and subtractions seem
fundamental to how the algorithm works, so we will count the work contributed by
these arithmetic operations.
for i = 1 to n do
low = roster[i].quiz[1]
sum = roster[i].quiz[1]
for j = 2 to m do
sum = sum + roster[i].quiz[ j]
//A
if roster[i].quiz[ j] < low then
low = roster[i].quiz[ j]
end if
end for
sum = sum − low
//S
write(“Total for student”, i, “is”, sum)
end for
Subtraction occurs at the line marked //S, which is executed once for each
pass through the outer loop (once for each student), a total of n times. Addition,
203
S e c t I o n 3 . 3 analysis of algoRithms
The General Idea
Often more than one algorithm can perform the same task. Because we assume that
all these algorithms perform correctly, we need some other basis of comparison to
decide which algorithm to use in a given situation. Several criteria could be used
to judge which is the “best” algorithm. We might ask, for example, which is easiest to understand, which makes the most efficient use of machine memory when
implemented as computer code, or which runs most efficiently. One might expect
that to judge whether an algorithm is “running efficiently” means standing by with
a stopwatch while the computer code executes. But the stopwatch approach may tell
us more about the speed of the processor than it does the inherent efficiency of the
algorithm. Even timing the code for competing algorithms on the same processor
and using the same input data can give a misleading picture of what might happen
when the input data set is larger.
Instead, we evaluate the time efficiency of an algorithm by estimating the
number of operations it must perform. We count only the operations that are
basic to the task at hand, not “housekeeping” operations that make just a small
contribution to the total work required.
The study of the efficiency of algorithms, that is, the number of operations
they perform, is called analysis of algorithms. Various techniques for algorithm
analysis have been developed. Sometimes a rather straightforward analysis can be
done simply by inspecting the algorithm.
example 27
Following is an algorithm to write out, for each student on a grade roster, the sum
of m quiz grades minus the lowest grade. The outer loop goes through each of the
n students; the inner loop goes through the quizzes for the current student. For each
student, the successive quiz grades are added and the lowest grade is ultimately
subtracted from the sum of all the grades. These additions and subtractions seem
fundamental to how the algorithm works, so we will count the work contributed by
these arithmetic operations.
for i = 1 to n do
low = roster[i].quiz[1]
sum = roster[i].quiz[1]
for j = 2 to m do
sum = sum + roster[i].quiz[ j]
//A
if roster[i].quiz[ j] < low then
low = roster[i].quiz[ j]
end if
end for
sum = sum − low
//S
write(“Total for student”, i, “is”, sum)
end for
Subtraction occurs at the line marked //S, which is executed once for each
pass through the outer loop (once for each student), a total of n times. Addition,