4. (15 points) Write a Java method to find the majority item of an unsorted array of size n. The majority element is the element that appears more than n/2 times. You may assume the array is non-empty and the majority element always exist in the array. Note that there is always one majority element. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 [Hint: Divide the array into halves, recursively find/return the majority of the first half of the way, ... If you do not get the hint, no big deal; there are many ways to solve this problem.] a) (10pts) Write the method: public int majorityElement (int[] nums) \& b) (3pts) Explain the running time of your method. c) (2pts) Write the big Oh notation for the running time