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.

3. Prove that Pr[M k log_2 n + 1] is at most 1/n^k1 .

4. Using the above facts, prove that the expected maximum level of all nodes is (log n).