The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
3.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})$

asked in Algorithms by Veteran (59.4k points)
retagged by | 3.3k views
0
Plz explain how to solve this problem...?

3 Answers

+32 votes
Best answer

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

 

answered by Boss (13.5k points)
edited by
0
Plz explain, that how consecutive fibonacci numbers will give the worst case? Is there any other method to solve?
+10
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)
+9
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

+12

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

 

+5 votes
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)$
answered by Active (2.4k points)
0
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) ..
answered by Boss (10.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,528 questions
42,803 answers
121,619 comments
42,166 users