In the following C function, let n >= m. c int gcd(n,m) { if (n%m ==0) return…
2007
In the following C function, let n >= m.
c
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.
Θ(logn)
- B.
Ω(n)
- C.
Θ(loglogn)
- D.
Θ(sqrt(n))
Attempted by 52 students.
Show answer & explanation
Correct answer: A
Answer: Θ(log n)
Reasoning:
Key idea: Each recursive call replaces the pair (n, m) with (m, n mod m), where the second value becomes strictly smaller than the previous second value. The sequence of remainders decreases quickly in the worst case.
Worst-case argument (Fibonacci): If the algorithm makes k recursive calls, then the initial pair must be at least consecutive Fibonacci numbers F_{k+1} and F_k. Since Fibonacci numbers grow exponentially (F_{k+1} ≥ φ^k / √5 where φ ≈ 1.618), we have n ≥ F_{k+1} ≥ c·φ^k for some constant c, so k = O(log n).
Tightness: There are inputs (consecutive Fibonacci numbers) that require Θ(log n) calls, so the bound is both an upper and lower bound; therefore the number of recursive calls is Θ(log n).
Conclusion: The Euclidean gcd implementation makes Θ(log n) recursive calls in the worst case.