3. Divide and Conquer (6 points) Let A[0..n -1| be an array of n numbers. A number in A is a majority element if A contains this number at least Ln/2 + 1 times. So for example, the array A 4, 3, 2,4,1,3,3,6, 3,3, 3,3} has 3 as its majority element. Write a divide-and-conquer algorithm that determines whether a given array A[0..n 1] contains a majority element, and if so, returns it. Your algorithm should run in O(n log n) time. You are not allowed to simply sort the array. Set up and solve a runtime recurrence for your algorithm Hint: Start by applying the generic divide-and-conquer approach. Try to divide by two. Then try to combine the results. From the given runtime you should be able to guess how much time you are allowed to spend for dividing and combining