DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 836

In the best case when m % n is 0 , the algorithm takes just one step to find the GCD. It is dif-
ficult to analyze the average case. However, we can prove that the worst-case time complexity
is O (log n ).
Assuming m

best case
average case

Ú n , we can show that m % n < m / 2 , as follows:

worst case

If n <= m / 2 , m % n < m / 2 , since the remainder of m divided by n is always
less than n .

■

If n > m / 2 , m % n = m - n < m / 2 . Therefore, m % n < m / 2 . ■

Euclid's algorithm recursively invokes the gcd method. It first calls gcd(m, n) , then calls
gcd(n, m % n) , and gcd(m % n, n % (m % n)) , and so on, as follows:

gcd(m, n)
= gcd(n, m % n)
= gcd(m % n, n % (m % n))
= ...

Since m % n < m / 2 and n % (m % n) < n / 2 , the argument passed to the gcd method
is reduced by half after every two iterations. After invoking gcd two times, the second
parameter is less than n /2. After invoking gcd four times, the second parameter is less than
n /4. After invoking gcd six times, the second parameter is less than n

2 3 . Let k be the number
of times the gcd method is invoked. After invoking gcd k times, the second parameter is less
than

n
2 ( k /2) , which is greater than or equal to 1. That is,
n
2 ( k /2)

2 ( k /2)

Ú = 7 Ú = 7 Ú = 7 …

1 n log n k /2 k 2log n

…

Therefore, k 2log n . So the time complexity of the gcd method is O (log n ).

The worst case occurs when the two numbers result in the most divisions. It turns out that
two successive Fibonacci numbers will result in the most divisions. Recall that the Fibonacci
series begins with 0 and 1, and each subsequent number is the sum of the preceding two num-
bers in the series, such as:

0 1 1 2 3 5 8 13 21 34 55 89 . . .

The series can be recursively defined as

fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index - 2) + fib(index - 1); index >= 2

For two successive Fibonacci numbers fib(index) and fib(index - 1) ,

gcd(fib(index), fib(index - 1))
= gcd(fib(index - 1), fib(index - 2))
= gcd(fib(index - 2), fib(index - 3))
= gcd(fib(index - 3), fib(index - 4))
= ...
= gcd(fib(2), fib(1))
= 1

For example,

gcd(21, 13)
= gcd(13, 8)
= gcd(8, 5)
= gcd(5, 3)