The following algorithm, Count Multiples, takes as input a list of n distinct positive integers and returns the number of list elements that are a multiple of some prior list element. For example, on the input 2,6,5,9,8, 3, 15, the algorithm would return 3 because there are 3 list elements that are a multiple of some prior list element: 6 is a multiple of 2 s is a multiple of 2 15 is a multiple of 5 (and it is a multiple of 3) procedure Count Multiples(ai,.. an n2 1) 1. if n-1 then return 0 2. count 0 4. for i=1 to n-1 5. if a, divides an then return m+1 6. return m (a) Prove that CountMultiples is correct. Proof: We can prove that CountMultiples is correct for any input of size n, using strong / weak (regular) induction on . For the base case, when n 1, CountMultiples returns 0 in line 1. This is correct because Now suppose as the inductive hypothesis that CountMultiples is correct on all inputs of size and we will show that it is correct on all inputs of size n, where n > 1. Let a1,... , an be an arbitrary input of size n. Therefore, since we have shown that for an arbitrary input of size n, Count Multiples(a,an) returns the number of elements in the input list that are a multiple of some prior list element, we conclude that CountMultiples is correct by induction. (b) Give an example of a best-case input of size n = 6, Write a recurrence for the runtime T(n) in the best case. What's the order of the algorithm in notation, in the best case? (c) Give an example of a worst-case input of size n = 6. Write a recurrence for the runtime T(n) in the worst case. What's the order of the algorithin in notation, in the worst case