News for hackers. Stuff that matters.
Re:A program to compute the nth Fibonacci number by drostie on Saturday April 28, 2012 @04:47PM (#3904058)
(1) The whole point of that "O(1) algorithm" is that the n'th Fibonacci number has asymptotic size:

    F[n] ~= phi ** n / sqrt(5) 
But this means that it requires O(n) memory to store, which means that it is impossible to get an algorithm which scales better than O(n), asymptotically. You might be able to get better than O(n²); I don't know much about arbtitrary-precision exponentiation algorithms.

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

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.