Answer question 1.3 (i.e. provide a theta/tight bound on the average case of the above algorithm). Thanks!

Consider the following algorithm, which operates on a non-empty array of integers: def evens_are_bad (1st): if every number in lst is even: repeat ist.length times: calculate and print the sum of lst return 1 else: return 0 1. Define the set of possible inputs and a probability distribution over this set. In this case, our set is all lists of length n that contain only ele- ments in the range 1-5, and the probability distribution is the uniform distribution. 1.3 Suppose we allow the all-evens check on line 2 of evens_are_bad to stop immediately after it finds an odd element. Perform a new average- case analysis for this mildly-optimized version of the algorithm using the same input distribution as in the notes. Hint: part of the running time T now can take on any value between 1 and n; first compute the probability of getting each of these values, and then use the expected value formula