0

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. SICP

0

1 Answer 1

1

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.

5
  • 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.
    – cnnrmnn
    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.
    – Doc Brown
    Mar 28, 2021 at 20:39
  • Doesn't the lower bound consider the best case?
    – cnnrmnn
    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.
    – Doc Brown
    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.
    – cnnrmnn
    Mar 30, 2021 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.