Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territo

Well, iterative (and smart tail recursive [0]) solutions are going to be roughly O(n) for the nth Fibonacci number, assuming addition is O(1). In bignum territory, addition isn't free, but is still pretty cheap. The closed form solution involves computing something raised to the power of n, so would be O(log n) assuming nonintegral multiplication is O(1), which is... not so much the case. Given that the (sqrt 5) factors will always be eliminated by the end you can manipulate things to work with only integers, at the expense of complicating the algorithm. The matrix-based solution, which I had forgotten, is also of the form x^n, so is probably isomorphic to a sufficiently clever handling of Binet's formula that completely avoids the (sqrt 5) terms. So, yes, good call, the matrix approach is better--you win this round. [0] The naive un-memoized recursive algorithm, such as the recursive solution in the linked article, is not only not tail-recursive, but manages to have time complexity of precisely O(fib(n)). If that doesn't make you die a little inside, you're made of sterner stuff than I.