just need part e)

(16 points) Consider the following algorithm to find the second largest number from an array S[1.n) 2. int max, max2; if (max = S[1]; max2 = S[2];} else (max = S[2]; max2-S[1];} For (i = 3; i max) (max2 = max; s[i];} max = else if (s[i] max2) (max2 = s[i]); For each element in S[3..n], what is the minimum/maximum number of (> comparisons that will be executed? What is the minimum total number of (>) comparison that need to be executed? What is the maximum total number of (>) comparison that need to be executed? Now consider the randomized version of the algorithm by permuting S randomly before executing the algorithm above. Let Y be the total number of () comparison that is need for a given input S. Let Xi (3 is n) = 1 if the "else if" line is executed for s[i] and 0 otherwise. Write Y in terms of X Show that the expected number of (>) comparison in the randomized algorithm is less than n -2+ 2log2n (Hint: 1+ 1/2+ 1/3 +....+ 1 s 1 + log2n) a. b. c. d. e