In this problem, consider a skip list with n >= 2 elements. As described in class, the height (number of levels) of each node is randomly determined. For simplicity, assume that n is a power of 2 (i.e. log2 n is an integer). Let M be the maximum level of all nodes. (log2 means log_2)

3. Prove that Pr[M >=k log2 n + 1] is at most 1/n^k-1 . 4. Using the above facts, prove that the expected maximum level of all nodes is (log n).

"The above facts" are these 2 points:

1. One specific node has at least k log2 n + 1 levels. 2. Pr[M log2 n + 1] is at least 1