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.

1. Compute the probability that one specific node has at least k*log_2 n + 1 levels.

2. Prove that Pr[M log_2 n + 1] is at least 1