208
Recursion, Recurrence Relations, and Analysis of Algorithms
Let C(n) represent the maximum number of comparisons required for an
n-element list. This is a symbolic expression for an answer we are assuming we
don’t already know, but will learn by solving the recurrence relation. By this notation, C(n − 1) symbolically represents the maximum number of comparisons
required to search the rest of the list after the first position. The recurrence relation is
C(1) = 1
(1 comparison to search a 1-element list)
C(n) = 1 + C(n − 1) for n
≥
2
(1 comparison against the first element,
then however many comparisons
are required for the rest of the list)
This is a first-order, linear recurrence relation with constant coefficients. By
Equation (8) in Section 3.2, the solution is
C(n) = (1)
n−1
(1) + ∙
n
i=2
(1)
n−i
(1) = 1 + (n − 1) = n
This agrees with our previous analysis for the worst case.
example 30
Now let’s do a worst-case analysis of the binary search algorithm. Recall that binary
search is a recursive algorithm that operates on a list that is sorted in increasing
order. It first does one comparison of the target with the midpoint value of the list.
If this comparison fails, then the process is repeated on the right half or the left half
of the list, depending on whether the target value is greater than or less than the
midpoint value. Figure 3.4 illustrates one possible worst-case path.
Search
here;
if fail,
not in list
Search
here;
Search
here;
if fail, test
for smaller or larger
Search
here;
if fail, test
for smaller or larger
if fail, test
for smaller or larger
Figure 3.4
Binary search is a divide-and-conquer algorithm, where the problem is
decomposed recursively into significantly smaller subproblems. If the original list
is n elements long, then half the list is at worst n/2 elements long. (In the 8-element
list of Example 14, for instance, when 10 is the midpoint value, the right “half” of
the list has 4 elements but the left “half” has only 3.) Cutting the list in half makes
much faster progress than reducing the list by one element, as in sequential search,
so we expect the worst case of binary search to require less work.
Recursion, Recurrence Relations, and Analysis of Algorithms
Let C(n) represent the maximum number of comparisons required for an
n-element list. This is a symbolic expression for an answer we are assuming we
don’t already know, but will learn by solving the recurrence relation. By this notation, C(n − 1) symbolically represents the maximum number of comparisons
required to search the rest of the list after the first position. The recurrence relation is
C(1) = 1
(1 comparison to search a 1-element list)
C(n) = 1 + C(n − 1) for n
≥
2
(1 comparison against the first element,
then however many comparisons
are required for the rest of the list)
This is a first-order, linear recurrence relation with constant coefficients. By
Equation (8) in Section 3.2, the solution is
C(n) = (1)
n−1
(1) + ∙
n
i=2
(1)
n−i
(1) = 1 + (n − 1) = n
This agrees with our previous analysis for the worst case.
example 30
Now let’s do a worst-case analysis of the binary search algorithm. Recall that binary
search is a recursive algorithm that operates on a list that is sorted in increasing
order. It first does one comparison of the target with the midpoint value of the list.
If this comparison fails, then the process is repeated on the right half or the left half
of the list, depending on whether the target value is greater than or less than the
midpoint value. Figure 3.4 illustrates one possible worst-case path.
Search
here;
if fail,
not in list
Search
here;
Search
here;
if fail, test
for smaller or larger
Search
here;
if fail, test
for smaller or larger
if fail, test
for smaller or larger
Figure 3.4
Binary search is a divide-and-conquer algorithm, where the problem is
decomposed recursively into significantly smaller subproblems. If the original list
is n elements long, then half the list is at worst n/2 elements long. (In the 8-element
list of Example 14, for instance, when 10 is the midpoint value, the right “half” of
the list has 4 elements but the left “half” has only 3.) Cutting the list in half makes
much faster progress than reducing the list by one element, as in sequential search,
so we expect the worst case of binary search to require less work.