3. Consider the following recursive algorithm, where array is an array of integers. You can assume that the length of array is a power of two, so len(array) is n =

2m for some m ≥ 0. (a) (1 marks) How many array accesses are made in total by calling squoogle (array)? An array access means that you evaulate array[i] for some i. Write your answer as a recursive formula in terms of m. You can treat the arguments to the recursive calls as if they do not require array accesses to compute. (b) (2 marks) Give a closed-form expression for your formula from part a) in terms of m. Prove your answer is correct using induction. (c) (0.5 marks) What is your closed-form expression from part b) in terms of n, the number of elements in the array?