4 ms·
Not to be pedantic, but while the computational complexity of the map.get() function is O(1), meaning that the number of computational steps executed is constan
by beisner 10y ago
Not to be pedantic, but while the computational complexity of the map.get() function is O(1), meaning that the number of computational steps executed is constant with the size, the runtime complexity is often O(f(N)), because cache fetches and disk fetch latency increase with the number of items stored, meaning that the amortized time of get() might be longer for larger datasets.
This doesn't invalidate your experience at all - the interviewer may or may not have been talking about this, and there may well be cultural issues there - but I learned this interesting distinction recently, figured I would pass it on.
- UK-AL 10y agoI thought the whole point of O Notation is that your not thinking about low level operations like Disk io or caching.. Just the growth of the operations performed.
- pjlegato 10y agoComputational complexity vs. runtime complexity: while the details are irrelevant for computational complexity, as you say, the runtime complexity is a different matter, because the execution environment (disk, cache, etc.) has been optimized to deliver better performance for certain types of operations. In the real world, it may thus be better to use a computationally more complex algorithm than a computationally simpler one in certain cases, if you happen to have a system that delivers big enough optimizations for the complex algorithm.