The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
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 (69k points)
retagged by | 3k views
Plz explain how to solve this problem...?

3 Answers

+31 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 Veteran (14.1k points)
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. 

 

+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 Loyal (2.7k points)
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 Veteran (23.9k 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

33,687 questions
40,231 answers
114,269 comments
38,800 users