5.6k 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 | 5.6k views
0
Plz explain how to solve this problem...?
0
+1
+1
For m=2 and for all n=2^i , running time is ϴ(1) which will contradicts every option...

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

Correct Answer: $A$

edited
0
Plz explain, that how consecutive fibonacci numbers will give the worst case? Is there any other method to solve?
+26
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)
+14
Some things we must know before :)
0

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

+15

@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.

0

F0=0,  F1=1, F2=1, F3=2, F4=3 ....

I have one doubt :

gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1

Did you mean

gcd(Fn,Fn−1) calls gcd(Fn−1,Fn−2) calls⋯gcd(F1,F0)=1?

If so then i don't think any pair of (Fn,Fn−1) where n>2 will call upto (1,0). It will stop at F3,F2

Eg:

gcd(8,5) calls gcd(5,3) calls gcd(3,2) calls gcd(2,1) which is equal to 1

gcd(2,1) : n=2 , m=1 n%m==0 so function returns m and does not call gcd(1,0).

Though this doesn't matter here but still I wanted to clarify.

This example would never have crossed my mind. Thanks a lot :)

0
@arjun sir,  how do we conclude the last line from the first paragraph of the explanation ? Please elaborate on how we got the number of recursive calls = O(log n) when we want to find gcd(n,m).
0
I didn't understand how golden ratio is contributing to the final answer, also how did we come to the conclusion that it is $\Theta (logn)$

Try to put input in worst case... edited
0
I couldn't understand what you are denoting by n/2, n/4 or m/2 ,m/4 and finally arriving at 1? If you could pls explain in detail
+1
34%21=13 closed to 17 i.e n/2

13%8=5 closed to 6 i.e (n/2)/2=n/4

and so on.Similarly for m.Here n and m alternatively change their position while executing.Finally got 1.
0
Okay
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)$
0
How to solve by simple way by applying recurrence relation?
• If you stare at the algorithm for sometime, you will see that the remainder is 'cut' into half in every 2 steps.
• And since it cannot go less than 1, there can be atmost 2.[log2n]2.[log2n] steps/recursions.
• Each step/recursion requires constant time, θ(1)θ(1)
• so this can be atmost 2.[log2n].θ(1)2.[log2n].θ(1) time
• and that's θ(logθ(log n)
–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) ..