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.
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.