A majority element in an array, A, of size N is an element that appears more than N/2 times(thus, there is at most one). If there is no majority element, your program should indicate this. Design two different algorithms and write them in Java. And then run these algorithms with four given sample sets(Majex1, 2, 3, 4) of input files and measure execution time for each case.

a) Method 1 (O(N2) algorithm: Write a program to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than N/2 then break the loops and return the element having maximum count. If maximum count doesn’t become more than N/2 then majority element doesn’t exist

b) Method 2 (O(NlogN) algorithm using a divided-and-conquer method. The algorithm begins by splitting the array in half repeatedly and calling itself on each half. When we get down to single elements, that single element is returned as the majority of its (1-element) array. At every other level, it will get return values from its two recursive calls. The pseudo-code of the algorithm is as follows:

procedure GetMajorityElement(a[1...n])
Input: Array a of objects
Output: Majority element of a
if n = 1: return a[1]
k = n/2
elemlsub = GetMajorityElement(a[1...k])
elemrsub = GetMajorityElement(a[k+1...n]
if elemlsub = elemrsub:
return elemlsub
lcount = GetFrequency(a[1...n],elemlsub)
rcount = GetFrequency(a[1...n],elemrsub)
if lcount > k+1:
return elemlsub
else if rcount > k+1:
return elemrsub
else return NO-MAJORITY-ELEMENT
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.