alt Hacker NewsO(1) simply means that there's a constant upper bound to the algorithm as n -> ∞.
In English: There is some worst-case time taken to compute the algorithm that adding any further `n` will not take any longer.
O(1) simply means that there's a constant upper bound to the algorithm as n -> ∞.
In English: There is some worst-case time taken to compute the algorithm that adding any further `n` will not take any longer.
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.