6. The following algorithm, Count Multiples, takes as input a list of n 2 1 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 8 is a multiple of 2 15 is a multiple of 5 (and it is a multiple of 3) procedure CountMultiples(a1, . an: n21) 1. if n = 1 then return 0 3. fori 1 to n-1 4, if ai divides an then return m+ 1 5. return m (a) (5 points) Prove that Count Multiples is correct. b) (3 points) 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) (3 points) 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 algorithm in notation, in the worst case