While watching lecture 1B of the Structure and Interpretation of Computer Programs, there's a function that calculates Fibonacci numbers. The lecturer points out that the time complexity is O(fib n) - I've never seen that before. I've seen it rounded to constant, linear, n+m, quadratic, polynomial, or exponential complexity, but are there any other O(fib n) algorithms or other interesting big O notations that should be looked at or studied?
Asked
Active
Viewed 812 times
2
-
Have you seen this: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it/46607#46607 – Gabe Jan 07 '11 at 07:18
1 Answers
3
O(fib N) is nothing strange or special - it is exactly the same thing as exponential complexity - it is just that the lecturer did not take the time to spell it out. (You can easily* bound fib(N) with phi^n.)
You don't have to believe me though - you would have a better explanation on Math.stackexchange.
*: I'll clarify what I mean by "easily" - it means that the proof is readily available, for example in that wikipedia article (thanks to the previous answerer that originally gave the link to it).
Jean Hominal
- 16,518
- 5
- 56
- 90