Hacker News Reader

Comment by bitmadness | Hacker News Reader

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.

View on HN

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

This kind of pedantry doesn't add anything to the discussion. We all know big-O notation is a theoretical abstraction.

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.

Reply on news.ycombinator.com