[TheBoff]

I don't think you've read the article, actually.

The key point is that he is trying to calculate arbitrarily large fibonacci numbers, and so the addition is itself an O(n) operation. This means that even after memoization, the complexity is still O(n^2), and he uses a number of tricks to reduce that.

[ubasu]

His way around that is to use the matrix recurrence relation, which is also there in SICP as an exercise.

But it's a nice discussion in any case.