3k views

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?

1. $\Theta(\log_2n)$

2. $\Omega(n)$

3. $\Theta(\log_2\log_2n)$

4. $\Theta(\sqrt{n})$

retagged | 3k views
Plz explain how to solve this problem...?

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)$.

edited by
Plz explain, that how consecutive fibonacci numbers will give the worst case? Is there any other method to solve?
understanding the worst case is not the problem

how the hell will we know that worst case will come for fibonacci series in GATE (under 3 min constraint)

if we check manually for non-fibonacci number the answer is clearly loglog(n)
Some things we must know before :)

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+1th Fibonacci numbers. And nth Fibonacci is of the order of 2n.

Now, we have n - so it will be of the order of (log n)th Fibonacci number and hence require log n recursive calls.

let T(m,n) be the total number of steps.

so, T(m,0) = 0,

T(m,n) = T(n, m mod n) on average

=>  $T(n) = \sum :{T(k,n)} from k=0 to n$

by using masters theorem you will get: $\approx \Theta (\log n)$
How to solve by simple way by applying recurrence relation?
–1 vote
If we consider worst case then it will be option a ... as an example take n=11 m=8 .. it will be Ceil(Logn) ..