retagged by
26,380 views
64 votes
64 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})$

retagged by

8 Answers

Best answer
63 votes
63 votes

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$

edited by
28 votes
28 votes

Try to put input in worst case...

edited by
4 votes
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)$
Answer:

Related questions

26 votes
26 votes
1 answer
1
Kathleen asked Sep 21, 2014
10,260 views
Consider the following C function:int f(int n) { static int r = 0; if (n <= 0) return 1; if (n 3) { r = n; return f(n-2) + 2; } return f(n-1) + r; }What is the value of ...
64 votes
64 votes
15 answers
2
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
50 votes
50 votes
8 answers
4
Kathleen asked Sep 21, 2014
31,722 views
What is the $\text{time complexity}$ of the following recursive function?int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); ...