worst case/ best case, big theta, induction proof

3. The following algorithm, CountMultiples, takes as input a list of m 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 Count Multiples (a n 1) 1. if n 1 then return o 2. count -0 3. m Count Multiples(a1 n-1) 4. for i 1 to n 1 5. if ai divides an then return m 1 6. return m (a) Prove that Count Multiples is correct. Proof: We can prove that CountMultiples is correct for any input of size n, using strong weak (regular) induction on n. For the base case, when n 1, Count Multiples returns 0 in line 1. This is correct because Now suppose as the inductive hypothesis that Count Multiples 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 1,..., an be an arbitrary input of size n 3. The following algorithm, CountMultiples, takes as input a list of m 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 Count Multiples (a n 1) 1. if n 1 then return o 2. count -0 3. m Count Multiples(a1 n-1) 4. for i 1 to n 1 5. if ai divides an then return m 1 6. return m (a) Prove that Count Multiples is correct. Proof: We can prove that CountMultiples is correct for any input of size n, using strong weak (regular) induction on n. For the base case, when n 1, Count Multiples returns 0 in line 1. This is correct because Now suppose as the inductive hypothesis that Count Multiples 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 1,..., an be an arbitrary input of size n