Problem in GCD function

#1

Find the Complexity of the given code.

int gcd(int n, int m)
{
if (n%m ==0) return m;
if (n < m) swap(n, m);
while (m > 0)
{
n = n%m;
swap(n, m);
}
return n;
}

can you please explain me how to calculate time complexity of this solution.

#2

hi @itismohiton, The worst case for calculation of gcd, is on any two consecutive Fibonacci numbers.

Since two consecutive Fibonacci numbers are relatively prime.

Eg. n= 8, m=13

swap 13 8

->> 5 8 ->> 3 5 ->> 2 3 ->> 1 2 ->> 1 1 …

From observation it is forming series of Fibonacci numbers … 8 5 3 2 1 1. for each step.

So for value N how many steps does it required to get till 0. which is O(logn base 2) from recursion tree of Fibonacci number. so the complexity of the code is O(logn)

for more mathematical proof refer : - https://www.quora.com/What-is-the-time-complexity-of-Euclids-GCD-algorithm

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.