GATE CSE 2007 | Question: 44

Question

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?

• A. $\Theta(\log_2n)$

• B. $\Omega(n)$

• C. $\Theta(\log_2\log_2n)$

• D. $\Theta(\sqrt{n})$

Comments

https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

---

For m=2 and for all n=2^i , running time is ϴ(1) which will contradicts every option...

---

https://stackoverflow.com/a/30687762/5982032

Answer 1

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$

Comments

good to read http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html 

- fibonacci series, got lot of properties (last digit, last 2 digit periodic etc)

-cormen 3rd ed pg 59, ex pg 108 (3rd ed), ch27 pg 776 (3rd given TC for finding ith fib number), pg 993 (given gcd has worst case when n , m are consecutive fibonacci number)

---

worst question by gate , i think this questions are made to leave or else you are going to lose your precious time!!!!

---

Yes, if you don't have sufficient background knowledge you'll lose time on such questions.

Answer 2

Try to put input in worst case...

Comments

Bhai, please explain @himanshu

---

@ankit3009  n is approaching 1  function call by function call that is we are dividing it through by 2 plot the function calls and you can observe it takessome  k function calls   those are (n/2 power k   )=1   equating it we will get logn

---

@ankit3009, take the worst case input like 97, 48 or whatever you wish.

And, do consider this fact (bolded):

int gcd(n,m)  {
    if (n%m == 0) return m;
    n = n%m;
    return gcd(m,n);
}

 

Give a shot, and still if you can't get, revert back with issue, more specifically where you're stuck on.

Answer 3

 

This is how I approached the Problem. 

Comments

Wait a minute!

---

how have u got this idea in the exam man😢

Answer 4

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

Comments

How to solve by simple way by applying recurrence relation?