How to find time complexity for this question?

#1

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;
}

#2

Hey @mehul.ai, 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