Write pseudocode for computing gcd(m,n) where m = 525 and n = 125 and calculate worst time complexity of the problem.
Answers
The GCD of any two numbers can be derived from following logic.
GCD of m and n can be drawn by subtracting from each other until they become same or one.
Example: m = 525 n = 125.
Step 1: m = 525 - 125 = 400 and n = 125
step 2: m = 400 - 125 =275 and n = 125
step 3: m = 275 - 125 = 150 and n = 125
step 4: m = 150 - 125 = 25 and n = 125
step 5: m = 25 and n = 125 - 25 = 100
step 6: m = 25 and n = 100 - 25 = 75
step 7: m = 25 and n = 75 - 25 = 50
step 8: m = 25 and n = 50 - 25 = 25
We will stop here as both numbers are same.
The GCD of 525 and 125 is 25.
The pseudo code for above logic is very easy
function gcd(a, b)
while a ≠ b
{
if a > b
a := a − b;
else
b := b − a;
}
return a;
The above function will stop when both a and b become same.
The worst time complexity of above algorithm happens when both numbers GCD is 1.
They get subtracted until they both become 1.
Example: 1 and 7 (6 loops)
Maximum possible loops are bigger number - 1.
Hence the worst case time complexity is o(n-1) = o(n).