We have n elements {x1, ..., xn} we want to hash into a table T of size s = 2n. Let us consider the following method of hashing these n elements into T: For each i = 1,..., n, do the following: 1....

Extracted text: We have n elements {x1, ..., xn} we want to hash into a table T of size s = 2n. Let us consider the following method of hashing these n elements into T: For each i = 1,..., n, do the following: 1. Pick a permutation of [1,..., s] uniformly at random. Call this permutation T; : [s] → [s], which maps each index to the element which ends up in that index. 2. Set j : : 1. 3. While T[T;(j)] has an element in it, increment j. 4. Place x; in T[T;(j)]. 1.1 Show that while inserting any ;, the probability that there are at least t iterations of the while loop in Step 3 is at most 2-t.