(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 req

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