Consider the following pseudo code to compute the greatest common divisor of two
ID: 3869857 • Letter: C
Question
Consider the following pseudo code to compute the greatest common divisor of two integers
def gcd (a, b) :
if ( b == 0) : return a
return gcd(b, a mod b)
where mod is the modulo operation, remainder after a is divided by b. Let us say the size of the input is the number of bits in the binary representation of the first argument a, and the basic operation is the recursive call.
i) Estimate the number of times the basic operation is performed.
ii) Comments on the space requirements.
Give detailed reasons.
Explanation / Answer
Please find my answer.
Please let me know in case of any issue.
Consider any two steps of the algorithm.
At some point, you have the numbers (a,b) with a>b.
After the first step these turn to (b,c) with c=a mod b, and after the second step the two numbers will be (c,d)
with d=b mod c.
Now think backwards. As d=b mod c, we know that b=kc+d for some k>0.
The smallest possibility is k=1, therefore b 1c + d = c+d.
From that result and from a>b we get a>c+d.
If we add the last two inequalities we just derived, we get that (a+b)>2(c+d).
In words, after each two consecutive steps the sum of the two numbers decreases to less than half of its original size.
Now look at the very first step of the algorithm. At the beginning, we have some (a,b) with a>b.
After the very first step we have (b,c) with c=a mod b, and clearly b>c.
Hence, after the very first step both numbers are at most equal to the smaller of the two input numbers.
Putting those two results together, we may conclude that the number of iterations (recursive calls in other implementations) is at most logarithmic in the smaller input number. In other words, the number of iterations is at most linear in the number of digits in the smaller input number.
To see that this analysis is asymptotically optimal, take (a,b)=(Fn+1,Fn) -- that is, two consecutive Fibonacci numbers.
Algo GCD(x,y)
{
// x >= y where x & y are integers
if(y==0)
return x
else
return (GCD(y,x%y))
}
Time Complexity :
1. Best Case :
Time: O(1)
if y is divisible of x, then Euclid GCD terminates in one call.
Space: O(1)
2. Worst Case:
Time: O(log n), when x, y are two consecutive Fibonacci numbers
Space : O(logn)