Practice question · Multiple choice
The Euclidean algorithm's worst case is a pair of consecutive Fibonacci numbers. Why would the slowest input be those in particular?
Hints
- Run gcd(13, 8) by hand. What is the quotient at each step?
- The algorithm is fast because remainders usually shrink quickly. What is the slowest possible shrink?
Show the answer
B. Because consecutive Fibonacci numbers make every quotient 1
Why
Every quotient comes out 1, so each step replaces (a, b) with (b, a−b), the least progress the algorithm can make. Lamé used exactly this to bound the running time, giving the first worst-case complexity analysis of any algorithm, centuries before the term existed.
Practise GCD and the Euclidean Algorithm
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.