Question

An array A [1...n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, a A₂ nd so there can be no comparisons of the form “is $\mathit{A}\mathbf{\left[}\mathit{i}\mathbf{\right]}\mathbf{>}\mathit{A}\mathbf{\left[}\mathit{j}\mathbf{\right]}$?”. (Think of the array elements as GIF files, say.) However you can answer questions of the form: “is ..?” in constant time.

(a) Show how to solve this problem in O(nlog n) time. (Hint: Split the array A into two arrays A₁ and of half the size. Does knowing the majority elements of A₁ and A₂ help you figure out the majority element of A? If so, you can use a divide-and-conquer approach.)

(b) Can you give a linear-time algorithm? (Hint: Here’s another divide-and-conquer approach:

• Pair up the elements of A arbitrarily, to get n/2 pairs
• Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them
  Show that after this procedure there are at most n/2 elements left, and that they have a majority element if A does.)

Short answer

1. It has been shown that the problem is solve in the given time O(nlog n) .
2. Linear Time algorithm is proposed with run time O(nlog n) .

Step-by-step solution

Solution of part (a)

To solve the issue in the shortest amount of time

• Divide the array into two parts of size n/2.
• Name the first array A₁ and the second array.
• Take this same majority component from. and call it m₁, then take the majority component from A₂.
• Determine if the number for m₁ or m₂ is more than the array A' size.

A majority of both the element is found using the following algorithm:

function $\left(s\left[1,...,m\right]\right)$

Input: an array of numbers $\left[1,...,m\right]$

Output: majority value of array s

if (m=1)

return $\left(s\left[1\right]\right)$

role="math" localid="1659777799481" $$\begin{gathered} mid=\left[m/2\right] \\ l\_elem=majority\left(s\left[1,...,mid\right]\right) \\ r\_elem=majority\left(s\left[mid+1,...,m\right]\right) \end{gathered}$$

if : $\left(l\_elem=r\_elem\right):$

return l_elem

$$\begin{gathered} l\_sum=frequency\left(s\left[1,...,m,\right],l\_elem\right) \\ l\_sum=frequency\left(s\left[1,...,m,\right],r\_elem\right) \end{gathered}$$

if : l_sum > mid + 1:

return l_elem

else if r_sum > mid + 1:

return r_elem

else

return no - majority - elememts

Algorithm to find the frequency of the algorithm:

function $frequency\left(s\left[1,...,m\right],elem\right)$

Input: an array of numbers $s\left[1,...,m\right]$

Output: count of element of the array s

for i = 1 to m :

if $\left(s\left[i\right]=elem\right)$

return count

Explanation:

• "majority" is indeed a divide-and-conquer method which it accepts this same array "$s\left[1,...,m\right]$" as an input argument and employs the divide-and-conquer approach.

• It returns s[1] after checking if the index of the final member of the array is equal to 1.

• Divide the size of the index by two to get the middle member in the array, and use the ceilings procedure to have the centre element & allocate this to the variables "mid"

• Have the overwhelming element of both the left and right arrays by executing the same majority method with half of the array as a parameter.

• Next, make sure that both components are equal.

If yes, return the majority element of the left array.

• Using the function frequency, determine the frequency of the majority element in the left and right arrays.

• Return the element if the count of the element in the left array is larger than half of the items in the array "$s[1,...,m]$".

• Otherwise, return the element if the count of the right array element is larger than half of the items in the array "$s[1,...,m]$".

• Alternatively, no-majority-elements will be returned.

As a result, in each function call, it splits an array split two as well as searches each array through constant division of a array until the element is located with a consistent amount of time..

It takes $T\left(\frac{n}{2}\right)$time to search each array and a linear time of O(n) to count the majority element.

The recurrence relation is shown below:

role="math" localid="1659779003024" $T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\right)$ …… (1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT\left(\frac{n}{2}\right)+O\left(n^c\right)$ …… (2)

By comparing equation (1) and (2), the value of “n^c” is “n”, “c” is 1, “b” is “2” and “a” is 2.

By master’s theorem, if the value of c = log_b a, then the running time is,

$T\left(n\right)=O\left(n^c\log n\right)$ …… (3)

Check if c = log_b a :

log_b a …… (4)

Substitute the value of “b” as “2” and “a” as “2” in equation (4).

log_b a = log_b 2 = 1

Thus, the value of log_b a is equal to “c”.

Substitute the value of “c” as 1 in equation (3). The running time of algorithm is shown below:

$\begin{array}{rcl}T\left(n\right)& =& O\left(n^1\log n\right)\\ & =& O\left(n\log n\right)\end{array}$

Therefore, the algorithm takes a run time of O(n long) .

Solution of part (b)

Solving the problem in linear time:

To begin, split the array into two halves of n/2 size.

• Let A₁ be the first array and A₂ be the second array.

• Take the majority element from A₁ and call it m₁ , and take the majority element from A₂ and call it m₂.

• Determine whether the count of m₁ or m₂ is more than the array A' size.

Linear time algorithm to find the majority of the element:

function majority_linear (s[1, ..., m])

Input: an array of numbers s[1, ..., m]

Output: majority value of array s

if ( m = 2 )

if $\left(m\left[1\right]=m\left[2\right]\right)$

return $\left(s\left[1\right]\right)$

else

return no - majority - elements

create array temp_array

for k = 1 to m:

if $s\left[k\right]=s\left[k+1\right]$

Insert s[k] into temp

K = k + 1

return majority_linear (s[1, ..., m])

Algorithm for search of the theory of algorithm:

Function frequency_linear (s[1, ..., m])

Input: an array of numbers s[1, ..., m]

Output: majority element of the array s

$$\begin{gathered} q=majority\_linear\left(s\left[1,...,m\right]\right) \\ count=frequence\left(s\left[1,...,m\right],q\right) \end{gathered}$$

if $count>\left[n/2\right]+1$:

return q

else

return no - majority-elements

Explanation:

• The function "majority linear" receives the array "s[1, ..., m] " as an input argument and finds the majority of the element.

• It verifies whether the index of the array's last member is equal to 2 and whether the first two items are the same before returning S[1]. Otherwise, no majority items will be returned.
• A temporary array is created.
• It then compares each pair of items in the array and adds them to the temporary array if they are equal.
• Finally, the temporary array is returned.
• Because the method verifies all of the array's items, it takes a linear amount of time O(n).
  • "frequency linear" is a method that finds the majority of an element using the array "s[1, ..., m] " as an input factor.
• It uses the "majority linear" function and obtains the result returned by it.
• Then, to acquire the count of the majority element, this returned element is put into the "frequency" function.
• Retrieve the most element if the dominant element is bigger than half of the elements in the array.
• Otherwise, no majority items are returned.
• Because the method verifies all of the array's items, it takes a linear amount of time O(n).

As a result, comparing each pair of elements in the array takes T(n/2) time, whereas counting the majority element requires O(n) time. The following is the recurrence relationship:

$T\left(n\right)=T(n/2)+O\left(n\right)$ …… (1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT(n/2)+O\left(n^c\right)$ …… (2)

By comparing equation (1) and (2), the value of “n^c” is “n”, “c” is 1, “b” is “2” and “a” is 1.

By master’s theorem, if the value of c > log_b a, then the running time is shown below:

$T\left(n\right)=O\left(n^c\right)$ …… (3)

Check if :

log_b a …… (4)

Substitute the value of “b” as 2 and “a” as 1 in equation (4).

log_b a = log_b 1 = 0

log_b a is less than the value of “c” which is 1.

Substitute the value of “c” as 1 in equation (3). So, the running time of algorithm is

$\begin{array}{rcl}T\left(n\right)& =& O\left(n^1\right)\\ & =& O\left(n\right)\end{array}$

Therefore, the algorithm takes a run time of O(n log n)