4 ms·
Because it takes n time to access n units of memory. Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead
by yxhuvud 2y ago
Because it takes n time to access n units of memory.
Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.
- xigoi 2y agoWhat if you allocate a huge chunk of memory and only use a small part of it? For example, checking if a list of numbers contains duplicates using a boolean array.
- Sharlin 2y agoIf your algorithm requires O(n) memory, any O(1) amount of memory can never be enough, no matter how huge. That's the entire point of O notation. And if your implementation of an algorithm allocates more space in the big-oh sense than it can actually touch (eg. O(n) space for O(log n) time or whatever), that's just a wasteful implementation. Doesn't make the algorithm itself require more space than it has time to actually use.
- ajuc 2y agoLet's say you have a lookup table and your algorithm looks up a value and returns it. O(n) space O(1) in time.
- yxhuvud 2y agon is some value depending on the size of the input, so if you have a look up table that is O(n), then that memory needs to be initialized somehow. If you have a fixed size lookup table then it is O(1), even if it is big.
- ajuc 2y agoCompile time fill a lookup table. Run time read 1 value from it. I call it O(1) in time, O(n) in memory. You call it O(1) in both, right? Now move the compile time code to runtime. I call it O(n) in time and memory. What do you call it? If your say O(n) in time and memory - why is moving the code changing its complexity? If you say still O(1) - then everything is O(1), thus proving P=NP among other things :) Either way your interpretation isn't very useful.