ext_215013 ([identity profile] blasdelf.livejournal.com) wrote in [personal profile] dtm 2008-07-22 12:43 am (UTC)

I figured this out too around the same time you did, while *overdoing* some homework:
In the classical fib(n) each x in [1..n] is calculated exactly fib(n-x+1) times, making it O(fib(n)), which is O(c^n) (with c < 2).


(3 comments)

Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting
 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.