Project ForgeAlgorithms
Complexity Analysis
GATE 2007
Hard
In the following C function, let n ≥ 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?
- Θ(log₂ n)
- BΩ(n)
- CΘ(log₂ log₂ n)
- DΘ(√n)
Explanation
This is the Euclidean algorithm. By Lamé's theorem, the number of recursive calls is O(log n) (with the worst case achieved by consecutive Fibonacci numbers), giving a tight Θ(log₂ n) bound.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.