Time complexity of Euclid's Algorithm

user_717442 0
Viewed 119374

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?

iteration big-o time-complexity algorithm
11 Answers

Here is the analysis in the book Data Structures and Algorithm Analysis in C by Mark Allen Weiss (second edition, 2.4.4):

Euclid's algorithm works by continually computing remainders until 0 is reached. The last nonzero remainder is the answer.

Here is the code:

unsigned int Gcd(unsigned int M, unsigned int N)
{

    unsigned int Rem;
    while (N > 0) {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    Return M;
}

Here is a THEOREM that we are going to use:

If M > N, then M mod N < M/2.

PROOF:

There are two cases. If N <= M/2, then since the remainder is smaller than N, the theorem is true for this case. The other case is N > M/2. But then N goes into M once with a remainder M - N < M/2, proving the theorem.

So, we can make the following inference:

Variables    M      N      Rem

initial      M      N      M%N

1 iteration  N     M%N    N%(M%N)

2 iterations M%N  N%(M%N) (M%N)%(N%(M%N)) < (M%N)/2

So, after two iterations, the remainder is at most half of its original value. This would show that the number of iterations is at most 2logN = O(logN).

Note that, the algorithm computes Gcd(M,N), assuming M >= N.(If N > M, the first iteration of the loop swaps them.)

user_123427820

Worst case will arise when both n and m are consecutive Fibonacci numbers.

gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1 and nth Fibonacci number is 1.618^n, where 1.618 is the Golden ratio.

So, to find gcd(n,m), number of recursive calls will be Θ(logn).

user_43869770

At every step, there are two cases

b >= a / 2, then a, b = b, a % b will make b at most half of its previous value

b < a / 2, then a, b = b, a % b will make a at most half of its previous value, since b is less than a / 2

So at every step, the algorithm will reduce at least one number to at least half less.

In at most O(log a)+O(log b) step, this will be reduced to the simple cases. Which yield an O(log n) algorithm, where n is the upper limit of a and b.

I have found it here

user_95709410
Related