Re:It Can Happen to You
by steerablesafe on Thursday March 04, 2021 @07:40AM
(#26341582)
Well-written complexity guarantees specify the operations they count. Otherwise sorting in O(n log(n)) also "sidesteps" the cost of comparison too.
[ Parent
| on HN ]
And the analysis of hashmaps is not such a well-written guarantee -- as you resize, you need a bigger hash function output to reach all possible buckets. A bigger hash function output, assuming you have to keep the avalanche effect to keep output well-scrambled, requires more computations.
Earlier discussion: https://news.ycombinator.com/item?id=9807739