3 ms·
> with O(1) memory access everywhere Isn't that technically correct? The access time is bounded by a constant, hence the 1 -- unless there's a tape in your mem
by jhgb 5y ago
> with O(1) memory access everywhere
Isn't that technically correct? The access time is bounded by a constant, hence the 1 -- unless there's a tape in your memory hiearchy. (That you always strive for a better constant is of course another matter.)
- snidane 5y agoIt can't be O(1) because to just search for a memory location you need at least a binary search. Since memory lookup is implemented in hardware it is treated as constant access. Of course this is all obscured by magnitudes of the memory hierarchy. For real systems such as databases, it is a better idea to treat random memory access as O(log n), which then justifies doing batch lookups and libear scans. All of this O(1) RAM access makes people confused and they never start thinking beyond the simple undergrad abstraction of a single cpu with a single layer of RAM.