Time complexity of Euclid's Algorithm

Question

I am having difficulty deciding what the time complexity of Euclid's greatest common denominator algorithm is. This algorithm in pseudo-code is:

function gcd(a, b)     while b ≠ 0        t := b        b := a mod b        a := t     return a 

It seems to depend on a and b. My thinking is that the time complexity is O(a % b). Is that correct? Is there a better way to write that?

Answer 1

One trick for analyzing the time complexity of Euclid's algorithm is to follow what happens over two iterations:

a', b' := a % b, b % (a % b) 

Now a and b will both decrease, instead of only one, which makes the analysis easier. You can divide it into cases:

• Tiny A: 2a <= b
• Tiny B: 2b <= a
• Small A: 2a > b but a < b
• Small B: 2b > a but b < a
• Equal: a == b

Now we'll show that every single case decreases the total a+b by at least a quarter:

• Tiny A: b % (a % b) < a and 2a <= b, so b is decreased by at least half, so a+b decreased by at least 25%
• Tiny B: a % b < b and 2b <= a, so a is decreased by at least half, so a+b decreased by at least 25%
• Small A: b will become b-a, which is less than b/2, decreasing a+b by at least 25%.
• Small B: a will become a-b, which is less than a/2, decreasing a+b by at least 25%.
• Equal: a+b drops to 0, which is obviously decreasing a+b by at least 25%.

Therefore, by case analysis, every double-step decreases a+b by at least 25%. There's a maximum number of times this can happen before a+b is forced to drop below 1. The total number of steps (S) until we hit 0 must satisfy (4/3)^S <= A+B. Now just work it:

(4/3)^S <= A+B S <= lg[4/3](A+B) S is O(lg[4/3](A+B)) S is O(lg(A+B)) S is O(lg(A*B)) //because A*B asymptotically greater than A+B S is O(lg(A)+lg(B)) //Input size N is lg(A) + lg(B) S is O(N) 

So the number of iterations is linear in the number of input digits. For numbers that fit into cpu registers, it's reasonable to model the iterations as taking constant time and pretend that the total running time of the gcd is linear.

Of course, if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be n^2 times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log* n). The polylogarithmic factor can be avoided by instead using a binary gcd.

Answer 2

The suitable way to analyze an algorithm is by determining its worst case scenarios. Euclidean GCD's worst case occurs when Fibonacci Pairs are involved. void EGCD(fib[i], fib[i - 1]), where i > 0.

For instance, let's opt for the case where the dividend is 55, and the divisor is 34 (recall that we are still dealing with fibonacci numbers).

As you may notice, this operation costed 8 iterations (or recursive calls).

Let's try larger Fibonacci numbers, namely 121393 and 75025. We can notice here as well that it took 24 iterations (or recursive calls).

You can also notice that each iterations yields a Fibonacci number. That's why we have so many operations. We can't obtain similar results only with Fibonacci numbers indeed.

Hence, the time complexity is going to be represented by small Oh (upper bound), this time. The lower bound is intuitively Omega(1): case of 500 divided by 2, for instance.

Let's solve the recurrence relation:

We may say then that Euclidean GCD can make log(xy) operation at most.