Recall that when a hash table gets to be more than about one half full, its performance quickly degrades. One solution to this problem is to reinsert all elements of the hash table into a new hash table that is twice as large.

Assuming that the (expected) average case cost to insert into a hash table is Θ(1), prove that the average cost to insert is still Θ(1) when this reinsertion policy is used.