The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+31 votes

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

5 Answers

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

Correct Answer: $A$

answered by Boss (13.2k 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. 


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

I have one doubt :


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


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 :)

@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).
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)$
+6 votes

Try to put input in worst case...

answered by Active (1.7k points)
edited by
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
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.
+4 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.6k points)
How to solve by simple way by applying recurrence relation?
0 votes
  • 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)
answered by Junior (663 points)
–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 (11.6k points)

Related questions

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
49,535 questions
54,120 answers
71,034 users