← Quiz: How Hashing Works: all 13 questions
Quiz: How Hashing Works · Question 8 of 13
Why is inserting into a hash map still O(1) on average even though resizing costs O(n)?
Why is inserting into a hash map still O(1) on average even though resizing costs O(n)?
- A.Resizing never happens
- B.Resizes are rare (the size doubles each time), so their cost spread over all inserts is O(1) each
- C.Resizing runs in a separate thread
- D.The O(n) is ignored by convention
Answer & explanation
Correct answer: Resizes are rare (the size doubles each time), so their cost spread over all inserts is O(1) each
Doubling means n inserts cause only O(n) total rehashing work — amortised O(1) per insert.
Can you get the rest right without peeking?
Take the timed Quiz: How Hashing Works quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →