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

5 Answers

+34 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.6k points)
edited by
0
Plz explain, that how consecutive fibonacci numbers will give the worst case? Is there any other method to solve?
+17
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)
+11
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

+14

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

+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.5k points)
0
How to solve by simple way by applying recurrence relation?
+4 votes

Try to put input in worst case...

answered by Junior (559 points)
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
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 (53 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.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

40,992 questions
47,620 answers
146,891 comments
62,346 users