My thoughts at this point in the original article was:
Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of the matrix [[1,0],[1,1]], and that the most efficient way to compute powers (in any associative domain) is the repeated squaring algorithm.
There are many ways to obtain the formula mentioned in the article. One of them is by diagonalizing this matrix and then applying exponentiation. How can another algorithm be better than constant time in the most general case?
No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N) bits.
Concretely Fibonacci(1480) is the largest Fibonacci number that fits into a double. So for higher Fibonacci numbers you need to compute this with arbitrary size integers (or floats). And then look at it in terms of bit complexity (i.e. the time to compute a product grows with the size of the integers).
Put differently. The "constant time" algorithm only works for N up to 1480. And if you limit N, then it doesn't really make sense to talk about the asymptotic complexity.
I believe the optimal algorithm is to compute the Fibonacci number by computing the N-th power of the matrix [[1,1],[1,0]], and compute the power using the repeated squaring algorithm. There are alternative formulations of that using identities for Fibonacci or Lucas numbers, but those identities basically correspond to squaring the matrix.
If you really want the asymptotically fastest algorithm you must use the fastest algorithm for integer multiplication (Harvey and van der Hoeven’s).
But even with the naive multiplication for arbitrary size integers you can compute Fibonacci(1000000) - which is a number with more than 200'000 digits - in less than a second. ;-)
