In the following C function, let $n \geq m$.
int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); }
How many recursive calls are made by this function?
$\Theta(\log_2n)$
$\Omega(n)$
$\Theta(\log_2\log_2n)$
$\Theta(\sqrt{n})$
http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/
https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm
Worst case will arise when both $n$ and $m$ are consecutive Fibonacci numbers.
$\text{gcd}(F_n, F_{n-1}) = \text{gcd}(F_{n-1},F_{n-2}) = \dots = \text{gcd}(F_1,F_0) = 1$
and $n^{th}$ Fibonacci number is $1.618^n$, where $1.618$ is the Golden ratio.
So, to find $\text{gcd} (n,m)$, number of recursive calls will be $\Theta (\log n) $.
I know Nth fibonacci no ,we can find in O(2^n)
but how we are getting GCD in O(log n) ???
@arjun sir plz help
@Priya No. We are not finding the nth Fibonacci number. We need 'n' recursive calls to find the GCD of nth and n+1^{th} Fibonacci numbers. And n^{th} Fibonacci is of the order of 2^{n}.
Now, we have n - so it will be of the order of (log n)^{th} Fibonacci number and hence require log n recursive calls.
Gatecse