Assumptions for
Thursday, Feb. 10, 2000
• Rehash whenever table is 50% full or more
• Just a sequence of inserts
– (can be generalized for other operations)
• We never get a collision
– (once dealing with collisions, we’re in average-
case analysis territory)
• Hash table starts as size 2