logoalt Hacker News

tsimionesculast Wednesday at 9:16 PM1 replyview on HN

Sure. And for any algorithm that needs to perform a read from memory, no such upper bound exists, this is the point.

For example, say we want to read the last number from an array. We get given the array index as an input, and we need to perform one memory read. You'd typically say that such an algorithm has a complexity of O(1).

However, if you actually write this algorithm and benchmark it for N=1, N=1MB, N=1GB, N=1TB, N=1PB and so on, you'll find that each of these is larger than the next. You'll also find that this number never stops growing. Accessing the last item in an array that is as large as a planet will take longer than accessing the last item in an array that is as large as a continent. So the actual complexity class is greater than O(1). Maybe O(n^1/3) is a good, maybe O(n^1/2) is better, maybe O(log n) would be best - whatever it is, it's not a constant.


Replies

b0gblast Wednesday at 9:23 PM

the last or the first... it's a matter of perspective... still relative </joke^2>