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?