204
Recursion, Recurrence Relations, and Analysis of Algorithms
however, occurs at the line marked //A. This is done within the inner loop, which
executes m − 1 times for each student, that is, for each of the n passes of the outer
loop. The total number of additions is therefore n(m − 1). The total number of
arithmetic operations is n + n(m − 1) = nm. Of course the value of this expression
depends on n (the number of students) and m (the number of quizzes). The quantities n and m measure the amount of input data; virtually any algorithm’s work will
change with the input size.
The algorithm also does some “housekeeping” work. Values are assigned
to variables, comparisons are done (to find the lowest quiz grade for each student), and for the loop indices i and j have to be incremented. But the number of
times these operations are done also depends on the number of times through the
loops, so their effect might be to multiply the nm result by some constant factor. In
comparing algorithms A and B, we’re usually looking for bigger differences than
just a constant multiple, which is why we ignore the housekeeping details.
Now suppose the task is to search a sorted list of n words or numbers for a
particular target value x. We already have one algorithm to perform this task, the
binary search algorithm from Section 3.1. Another algorithm for the same task, the
sequential search algorithm, simply compares x with each entry in the list in turn
until either x is found or the list is exhausted. (This algorithm actually works on any
list, sorted or not.) A pseudocode description of the sequential search algorithm is
given in the following box.
algorIthm SequentialSearch
SequentialSearch(list L; integer n; itemtype x)
//searches a list L of n items for item x
Local variable:
integer i
//marks position in the list
i = 1
while L[i] ∙ x and i < n do
i = i + 1
end while
if L[i] = x then
write(“Found”)
else
write(“Not found”)
end if
end function SequentialSearch
Both binary search and sequential search work by comparing elements from
the list with the target value x until a match is found. In fact it is difficult to imagine how any possible search algorithm could avoid such comparisons, so these
comparisons will be the basic operation to count in analyzing these two algorithms.
Recursion, Recurrence Relations, and Analysis of Algorithms
however, occurs at the line marked //A. This is done within the inner loop, which
executes m − 1 times for each student, that is, for each of the n passes of the outer
loop. The total number of additions is therefore n(m − 1). The total number of
arithmetic operations is n + n(m − 1) = nm. Of course the value of this expression
depends on n (the number of students) and m (the number of quizzes). The quantities n and m measure the amount of input data; virtually any algorithm’s work will
change with the input size.
The algorithm also does some “housekeeping” work. Values are assigned
to variables, comparisons are done (to find the lowest quiz grade for each student), and for the loop indices i and j have to be incremented. But the number of
times these operations are done also depends on the number of times through the
loops, so their effect might be to multiply the nm result by some constant factor. In
comparing algorithms A and B, we’re usually looking for bigger differences than
just a constant multiple, which is why we ignore the housekeeping details.
Now suppose the task is to search a sorted list of n words or numbers for a
particular target value x. We already have one algorithm to perform this task, the
binary search algorithm from Section 3.1. Another algorithm for the same task, the
sequential search algorithm, simply compares x with each entry in the list in turn
until either x is found or the list is exhausted. (This algorithm actually works on any
list, sorted or not.) A pseudocode description of the sequential search algorithm is
given in the following box.
algorIthm SequentialSearch
SequentialSearch(list L; integer n; itemtype x)
//searches a list L of n items for item x
Local variable:
integer i
//marks position in the list
i = 1
while L[i] ∙ x and i < n do
i = i + 1
end while
if L[i] = x then
write(“Found”)
else
write(“Not found”)
end if
end function SequentialSearch
Both binary search and sequential search work by comparing elements from
the list with the target value x until a match is found. In fact it is difficult to imagine how any possible search algorithm could avoid such comparisons, so these
comparisons will be the basic operation to count in analyzing these two algorithms.