The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost ac

The trick with O and hash tables is to remember that they're amortized O(1). Imagine a bag with the cost of resizing sitting inside it. Then, spread the cost across all inserts. There are always more inserts than the cost of resizing, so you end up w/ amortized O(1).