210
Recursion, Recurrence Relations, and Analysis of Algorithms
that fall between powers of 2. That’s why limiting n to powers of 2 in our analysis
is not particularly significant.
Upper Bound (Euclidean Algorithm)
The Euclidean algorithm, as presented in Section 2.3, uses a while loop to do
successive divisions to find gcd(a, b) for positive integers a and b, a > b. To
analyze the Euclidean algorithm, we must first decide on the operation we are
counting. Because the Euclidean algorithm does repeated divisions, we’ll take the
division operation as our unit of work. Because a > b, we can take a as a measure
of the size of the input values (which we usually denote by n). We want to find E(a),
where this denotes the amount of work (the number of divisions) required to find
gcd(a, b) in the worst case.
A recursive version of the Euclidean algorithm can also be written (see
Exercise 81, Section 3.1); the key to the recursive version is to recognize that
gcd(a, b) involves finding gcd(b, r), where r is the remainder on dividing a by
b. We’ve just seen a case where the operations of a recursive algorithm (binary
search) could be expressed neatly as a recurrence relation where the input size gets
halved after each operation. A recurrence relation would express E(a) in terms of
E at smaller values. But what are these smaller values? To find gcd(a, b) we find
gcd(b, r), so it is clear that the input size is getting smaller, but in what way? Consider Example 27 of Section 2.3, where to find gcd(420, 66) the following divisions
were performed:
6
2
1
3
66q420
24q66
18q24
6q18
396
48
18
18
24
18
6
0
Here the successive values being divided are 420, 66, 24, 18. The change from
420 to 66 is much larger than cutting in half, while the change from 24 to 18 is less.
In fact, we won’t find a recurrence relation or an exact expression for E(a). But
we will at least find an upper bound for E(a). An upper bound is a ceiling on the
amount of work an algorithm does; the algorithm can require no more steps than
the upper bound, but it may not require that many.
To find this upper bound, we will show that if i > j and i is divided by j with
remainder r, then r < i/2. There are two cases:
1. If j ≤ i/2, then r < i/2 because r < j.
2. If j > i/2, then i = 1 * j + (i − j); in other words, the quotient is 1 and r is
i − j, which is < i/2.
In the Euclidean algorithm, the remainder r at any step becomes the dividend
(the number being divided) two steps later. So the successive dividends are at least
halved every two divisions. The value a can be halved log n times, therefore at
most 2 log n divisions are done. Thus
E(a) ≤ 2 log a
(1)
The value of 2 log a for a = 420 is almost 18, whereas it took only 4 divisions
to find gcd(420, 66). Evidently this upper bound estimate is rather loose, like
saying that every student in this class is under 12 feet in height. An improved (that
is, lower) upper bound is derived in Exercises 37–40 at the end of this section.
Recursion, Recurrence Relations, and Analysis of Algorithms
that fall between powers of 2. That’s why limiting n to powers of 2 in our analysis
is not particularly significant.
Upper Bound (Euclidean Algorithm)
The Euclidean algorithm, as presented in Section 2.3, uses a while loop to do
successive divisions to find gcd(a, b) for positive integers a and b, a > b. To
analyze the Euclidean algorithm, we must first decide on the operation we are
counting. Because the Euclidean algorithm does repeated divisions, we’ll take the
division operation as our unit of work. Because a > b, we can take a as a measure
of the size of the input values (which we usually denote by n). We want to find E(a),
where this denotes the amount of work (the number of divisions) required to find
gcd(a, b) in the worst case.
A recursive version of the Euclidean algorithm can also be written (see
Exercise 81, Section 3.1); the key to the recursive version is to recognize that
gcd(a, b) involves finding gcd(b, r), where r is the remainder on dividing a by
b. We’ve just seen a case where the operations of a recursive algorithm (binary
search) could be expressed neatly as a recurrence relation where the input size gets
halved after each operation. A recurrence relation would express E(a) in terms of
E at smaller values. But what are these smaller values? To find gcd(a, b) we find
gcd(b, r), so it is clear that the input size is getting smaller, but in what way? Consider Example 27 of Section 2.3, where to find gcd(420, 66) the following divisions
were performed:
6
2
1
3
66q420
24q66
18q24
6q18
396
48
18
18
24
18
6
0
Here the successive values being divided are 420, 66, 24, 18. The change from
420 to 66 is much larger than cutting in half, while the change from 24 to 18 is less.
In fact, we won’t find a recurrence relation or an exact expression for E(a). But
we will at least find an upper bound for E(a). An upper bound is a ceiling on the
amount of work an algorithm does; the algorithm can require no more steps than
the upper bound, but it may not require that many.
To find this upper bound, we will show that if i > j and i is divided by j with
remainder r, then r < i/2. There are two cases:
1. If j ≤ i/2, then r < i/2 because r < j.
2. If j > i/2, then i = 1 * j + (i − j); in other words, the quotient is 1 and r is
i − j, which is < i/2.
In the Euclidean algorithm, the remainder r at any step becomes the dividend
(the number being divided) two steps later. So the successive dividends are at least
halved every two divisions. The value a can be halved log n times, therefore at
most 2 log n divisions are done. Thus
E(a) ≤ 2 log a
(1)
The value of 2 log a for a = 420 is almost 18, whereas it took only 4 divisions
to find gcd(420, 66). Evidently this upper bound estimate is rather loose, like
saying that every student in this class is under 12 feet in height. An improved (that
is, lower) upper bound is derived in Exercises 37–40 at the end of this section.