Hacker News new | past | comments | ask | show | jobs | submit login

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.




It's typically not counting comparisons, there are none when inserting elements. But sometimes it pretends that comparisons are O(1).




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: