In this problem, you are given a sorted int array data of size N (sorted in ascending order), where each element of data is some value between 0 and M 1, along with an int array counts of size N. You must write a recursive method that counts the number of occurrences of each element in the data array. For example, if you are given the array data = { 0, 1, 1, 1, 2, 2, 3, 4, 4, 4 }, with N = 10 and M = 5, then after your recursive method returns, the counts array should look like this: counts = { 1, 3, 2, 1, 3 }. You may assume that M = counts.length. (a) Give the most efficient recursive algorithm that you can think of that solves this problem. Give your solution in the form of an implementation of the following method:

b)Give the recurrence formula for the worst-case running time of your countsRec algorithm, assuming N = 2^k, where k is a non-negative integer.

static void countsRec(int[] data, int low, int high, int[] counts) { // Counts the occurrences of the elements in // data[low), ..., data [high] // Returns with counts [0] = # occurrences of 0 in data, // counts [1] # occurrences of 1 in data, etc. // If you leave this part blank, you will automatically earn // 6 points and I will ignore your answers on the next page