You can assume that the programming language is Python.

A CON 1 Search42 (L): z = L. head while z != None and z.key != 42: z = z.next return Z Suppose that the input list L has n (2 25) elements (excluding the None element). The list is constructed randomly as follows: The first number in the list is picked uniformly randomly from the set of all even numbers between 2 and 2n (both inclusive), i.e., {2,4,6,8,10, ..., 2n}, the second number in the list is picked uniformly randomly from the set of all even numbers between 4 and 2n inclusive, i.e. {4,6,8,10,..., 2n}, etc. Generally, the kth element in the list is picked uniformly randomly from {2k, 2(k + 1), ..., 2n}. All choices are made independently of each other. (a) (2 points) What is the smallest number of times line 3 is executed? What is the probability that line 3 is executed the smallest possible number of times? Justify your answer carefully: show your work and explain your calculation. (b) (3 points) What is the largest number of times line 3 is executed? What is the probability that line 3 is executed the largest possible number of times? Justify your answer carefully: show your work and explain your calculation. (c) (4 points) What is the expected number of times line 3 is executed? Justify your answer carefully: show your work and explain your calculation