Re:On calculating Fibonacci numbers in C
by stephencanon on Monday January 28, 2013 @09:06PM
(#5131951)
My analysis holds for any implementation for which you can perform O(1) addition and multiplication of integers of some fixed-size. That's just about as platform-independent as you can get, but it still captures the real complexity of the operation in a way that handwavy "pretend you can do arbitrary arithmetic in O(1)" analyses do not.
This isn't simply my viewpoint on the subject; even the very theoretical textbook by Papadimitriou and Vazirani takes this approach to the question (see exercise 0.4 and note that everything is carried out in terms of the complexity of arbitrary-size integer multiplication M(n)).
That's not to say you shouldn't take it into account, but the algorithm he described is, in fact, O(log(n)) time. It just is. That's how the math works. Now, you should note that the O(log(n)) time constraint does not take into account arbitrary integer size which will cause progressively larger constant factors to influence the efficiency of the algorithm... but it is still a O(log(n)) algorithm.