5 ms·
It seems the author hasn't read SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 http://mitpress.mit.edu/sicp/full-text/book/book
by ubasu 15y ago
It seems the author hasn't read SICP:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
- snissn 15y agosimilarly http://www.cs.berkeley.edu/~vazirani/algorithms/chap0.pdf http://www.cs.berkeley.edu/~vazirani/algorithms/chap0.pdf
- TheBoff 15y agoI 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 15y agoHis 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.