3 ms·
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.
by jplrssn 3y ago
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.
- mikebenfield 3y agoBig 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.
- charcircuit 3y agoBig 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.
- xvedejas 3y agoIt depends what you mean by "numbers": all integers or just 64-bit ones?
- deleted 3y ago[deleted]
- charcircuit 3y agoMy 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.
- utopcell 3y agoThe 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.