How does Lamé's Theorem give us an order-of-growth estimate for Euclid's Algorithm?

I'm reading SICP, and I don't understand how Lamé's Theorem gives us an estimate for the order-of-growth of Euclid's algorithm (the relevant passage is below). It would make sense to me if the assertion was that the smaller of the two inputs grows as the logarithm (to the base phi) of k. Intuitively, it makes sense to me that the number of steps k would increase with the smaller of the two inputs n, but it seems like all we've proven is that the smaller of the two inputs n grows with the number of steps k. Since all we've proven is that n must be at least Fib(k), I don't see how we can make any claims that k must grow with n, only that n must grow with k.

In my edition of SICP (first edition from 1987), the final sentence in that paragraph contained indeed `O(log n)`, not `Theta(log n)`, which fits to your observation - the provided proof literally just gives an upper bound for the order of growth of the algorithm.

However, in the second edition (online version here) it seems authors had replaced `O` by `Theta`. I guess they did so because `log n` is indeed a lower bound for the order of growth of the Euclidean algorithm.

Look first what we are measuring here: the Euclidean algorithm takes two parameters, n and m with n<=m. Let us define the number of steps as `E(n,m)`. To make this dependend just on n, we set

`````` f(n) := max_{m>=n}( E(n,m) )
``````

This maximum exists because of Lamés theorem, which is saying, when `n < Fib(k+1)`, then `E(n,m)` must be `<=k` for all m, which means `f(n)<=k`. When we speak about `O(log(n))` or `Theta(log(n))` of the "number of steps of the Euclidean algorithm", we actually mean the order of growth of this function `f`.

On the other hand, when `Fib(k) <= n < F(k+1)`, it is simple to see that `f(n)` must be also greater or equal to `k`: just set `m:= n +Fib(k-1)`. Starting the Euclidean algorithm with `(n,m)` leads to `(Fib(k-1), Fib(k))` in the first step, and then to the Fibonacci sequence in reverse order, hence requiring k steps.

So this gives you the lower bound for `f(n)`, and Lamés theorem the identical upper bound.

• Really appreciate the explanation. It makes sense to me that Lamé's Theorem would justify the upper bound. However, I don't see how `log n` is also a lower bound for the order of growth of the algorithm. Two consecutive Fibonacci numbers represent the worst case input to the algorithm. For any arbitrarily large `n` (the smaller number in the pair), the algorithm takes only one step if the larger number in the pair is a multiple of `n`. Mar 28, 2021 at 20:17
• @cnnrmnn: sure, but I think for a given n, we do not have to count the number of steps for a specific second number m>=n, but for the worst case of all possible pairs (n,m). See my edit. Mar 28, 2021 at 20:39
• Doesn't the lower bound consider the best case? Mar 28, 2021 at 21:43
• @cnnrmnn: orders of growth for an algorithm can be analysed for the best case, the worst case, or the average case of an algorithm, these aspects are orthogonal. See my edit. Mar 29, 2021 at 5:31
• Thanks for the thorough explanation. All makes sense to me now. Main thing that helped me wrap my head around it was realizing that since this algorithm has two inputs, the number of steps the algorithm uses given the smaller input depends on the larger input. It seems so obvious to me now, but analyzing the order of growth with respect to only one input distracted me from this fact. Mar 30, 2021 at 16:14