4 ms·
Big O notation is typically counting comparisons, and ignores constant factors. It isn't that memory hierarchy is ignored so much as the equating of comparison
by geophile 10y ago
Big O notation is typically counting comparisons, and ignores constant factors. It isn't that memory hierarchy is ignored so much as the equating of comparison growth (in n) with performance.
The field of cache oblivious algorithms is focused explicitly on memory hierarchy, and accounts for cache misses.
- SamReidHughes 10y agoIt's typically not counting comparisons, there are none when inserting elements. But sometimes it pretends that comparisons are O(1).