7 ms·
The author incorrectly states that the k-th Fibonacci number can be computed in O(1) time. Actually the algorithm he describes runs in O(k) time.
by bitmadness 7y ago
The author incorrectly states that the k-th Fibonacci number can be computed in O(1) time. Actually the algorithm he describes runs in O(k) time.
- dvt 7y agoWhat 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."
- continuational 7y agoIn 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)).
- dvt 7y agoThis kind of pedantry doesn't add anything to the discussion. We all know big-O notation is a theoretical abstraction.
- continuational 7y agoI 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.