Question 2: Average-Case Analysis [6 marks] Consider the following program called FindNemo that takes a list of strings as the input, and outputs the first index that holds the string "Nemo". We want to analyze the runtime of this program by counting how many times Line \#3 is executed, i.e., the number of comparisons made. Let n denote the length of the input L. Input distribution: The sample space consists of all permutations of a list of distinct strings ["Alice", "Bob", "Nemo", ... "Charlie"]. The length of the list is at least 3 and "Nemo" must exist in the array. These permutated lists are distributed in such a way that the string "Nemo" is equally likely to appear at any index from 2 to n1, and "Nemo" never appears at index 0 (the starting index) or index 1. Answer the following questions. (a) In the best case, what is the number of comparisons made by FindNemo? Write your answer in the blank below. The answer should be a number or an expression in terms of n. No justification required. Answer: (b) What is the probability of the best case? Write your answer in the blank below. The answer should be a number or an expression in terms of n. No justification required. Answer: (c) In the worst case, what is the number of comparisons made by FindNemo? Write your answer in the blank below. The answer should be a number or an expression in terms of n. No justification required. Answer: (d) What is the probability of the worst case? Enter your answer in the box below. The answer should be a number or an expression in terms of n. No justification required. Answer: (Continued on the next page...) Page 6 of 12 (e) In the average case, what is the expected number of comparisons made by FindNemo? Show your steps of calculation in the space below and clearly indicate your final result. The final answer should be an expression in terms of n and must be as simplified as possible. Note: Be concise. Concise and clear answers will be given higher marks than ambiguous and unnecessarily lengthy answers