Skip to content
GATETECH
Official PYQ · 2007Q44Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2007 Q44 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

In the following C function, let n≥mn \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?

Choose one option
View worked solution

Answer: A

The given C function implements the classic Euclidean algorithm for computing the Greatest Common Divisor (GCD) of two integers nn and mm (where n≥mn \ge m).

Let's analyze the reduction in each step of the recursion:

  • In the first call, if n(modm)==0n \pmod m == 0, the function terminates immediately with 00 recursive calls.
  • Otherwise, it updates n←n(modm)n \leftarrow n \pmod m and makes a recursive call gcd(m, n).

To find the upper bound on the number of recursive steps, we consider the worst-case input. The worst-case behavior of the Euclidean algorithm occurs when nn and mm are consecutive Fibonacci numbers:

n=Fkandm=Fk−1n = F_k \quad \text{and} \quad m = F_{k-1}

For consecutive Fibonacci numbers, each step reduces the pair to the next smaller pair of Fibonacci numbers:

gcd(Fk,Fk−1)→gcd(Fk−1,Fk−2)→…\text{gcd}(F_k, F_{k-1}) \to \text{gcd}(F_{k-1}, F_{k-2}) \to \dots

This requires exactly k−2k-2 recursive steps to reach the base case.

Using the approximation for Fibonacci numbers via the golden ratio ϕ=1+52≈1.618\phi = \frac{1+\sqrt{5}}{2} \approx 1.618:

Fk≈ϕk5  ⟹  k≈log⁡ϕ(n)F_k \approx \frac{\phi^k}{\sqrt{5}} \implies k \approx \log_{\phi}(n)

Thus, the number of recursive steps in the worst case is proportional to log⁡ϕ(n)\log_{\phi}(n), which is Θ(log⁡2n)\Theta(\log_2 n) because the base of the logarithm only changes the complexity by a constant factor.

Therefore, the number of recursive calls is Θ(log⁡2n)\Theta(\log_2 n).

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions