and 
.
Consecutive Fibonacci numbers are the worst-case input for Euclid's algorithm.
Thus, the worst-case run time for Euclid is the inverse Fibonacci
function for a (minus 2), which itself is bounded between
and .
We will next develop a (less precise, but more convenient)
short-hand notation for this: The running time of Euclid is
.
