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

Euclidian GCD worst case is when we have Fiboonacci pairs involved

As Arjun said, we must know this before.

Now think about the best case and average case time complexity of this algorithm

Option B : logn

Answer 2

If we consider worst case then it will be option a ... as an example take n=11 m=8 .. it will be Ceil(Logn) ..

Comments

For calculating GCD(n,m) EveryTime we are just dividing by m . So T(n) =T(m/n)+O(1) which 2nd case of masters method solving it complexity comes to be O(logn).

---

could you please elaborate it

Answer 3

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

Answer 4

Euclidean algorithm - Codility

Go through it