Flashcard
Amortized Analysis: Dynamic Arrays & Hash Tables
Why dynamic array append and hash table insert are O(1) amortized despite occasional O(n) resizes.
Question
Why are dynamic array append and hash table insert O(1) amortized, and why must growth be multiplicative?
Click to reveal answer