This is really a derivation of the Binet formula for Fibonacci numbers: that u_n = (phi^n - (-phi)^n) / sqrt(5), where phi is the golden ratio (1 + sqrt(5))/2.
What he states is that if n <= k, then we run in O(1) time, which is correct, because array lookup is O(1):
return fibonacci[k]
This is the canonical benefit of memoization, further clarified by this quote: "This solution has an O(k) space and time complexity for the first query."
In reality, array lookup is not O(1). It's orders of magnitude faster to do random lookups in an array that fits in L1 cache than one that doesn't. The cache hierachy makes array lookups O(log(n)) or possibly even O(sqrt(n)).
I think you overestimate the number of programmers that know this. In my experience, < 50% of programmers know that random array lookups are not constant time in practice.
I mean they would be able to deduce it, but they just never made the connection.
n^th Fibonacci number requires O(n) bits. So, saying the solution is O(log(n)) is kinda not true. I mean there cannot be a o(n) algorithm for computing decimal representation of n^th fibonacci number.
As always, it depends on your computational model. People are awful at specifying a model, in other words it's unclear what's even being stated.
You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.
And even if the model is sufficiently specified, the constant factors and lower terms hidden in the O-notationen can be deciding in practice, and are yet usually left out.
13 comments
[ 2.4 ms ] story [ 37.7 ms ] threadI mean they would be able to deduce it, but they just never made the connection.
You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.