Hacker News Reader

I’m struggling to understand this argument. The size of memory that you can address on any particular hardware is fixed, just like the word size for additions. Restricting yourself to a smaller part of that address space in software won’t change anything about how the address is decoded.

View on HN

Big O notation deals with asymptotic behavior of a function - in other words, as N goes to infinity. If we're accepting the premise that N has an upper bound, the rest of the discussion is meaningless.

Presumably the argument is an abstract one, not applying to any particular machine that actually exists.

Big O notation is often used with assumptions like adding numbers is always constant time. You can't physically build a machine where addition between any two numbers is constant time, but that doesn't matter.

It depends what you mean by "numbers": all integers or just 64-bit ones?

My point is relevant to additions that are the same type as n as n has no upper bound. n will never be a 64 bit integer.

The argument makes sense once you think of memory as a hierarchy of different sizes. The log of the size of the set of registers is smaller than the logs of the sizes of Li caches, which in turn are smaller than the log of the size of main memory.

Reply on news.ycombinator.com