GCD using modulo operator

Question

Could anyone explain the complexity of function (finding GCD) using modulo operator

Answer 1

Lets see the code of finding GCD using modulo first.Here let us say , a > b , so at 1st function call gcd(a,b) , a is the dividend and b is the divisor.

function gcd(a, b)
    if b = 0
       return a;
    else
       return gcd(b, a mod b);

So we know that the division step takes logarithmic time.Take an example :

Let we have a number , say n = 8.

We divide it by 2 till we get n = 1.So no. of steps involved ,

                              =  n / 2^k = 1

                              = k   =   O(logn)

So we can see that division operation takes O(logn) time.Simlarly in the above method of finding GCD , we are using the remainders as the divisor in the next step and the current divisor as the next dividend.So using modulo method is undergoing division method only.

Hence the complexity of this method is O(loga)  [Since we have already assumed a > b].

Comments

@Habibkhan , why are you assuming a>b because solution works well even for a<b

Assume i have to find GCD of 10,3 if i pass a>b ,then it will be  GCD(10,3)

Now here, next recursive call will be (3,1)

Now assume i pass :- GCD(3,10),now in next call it will be (10,3) which will becomes same as the first call in previous method.Its just that it took 1 extra step but we need not to worry about a<b or a>b