Re:A program to compute the nth Fibonacci number
by huggah on Saturday April 28, 2012 @05:57PM
(#3904245)
My apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O.
I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.
(2) This is one of those nasty cases where CS folks are loose with the meaning of big-O, anyway. Strictly speaking the input size for the Turing machine scales like O(log n), and so the Fibonacci algorithms should probably be said to have exponential complexity, even though it's a linear recurrence relation. It depends how loose you are with what the 'n' means in O(n).