Question

An array $\mathbf{A}[\mathbf{1}...\mathbf{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, and so there can be no comparisons of the form “ is $\mathbf{A}\left[\mathbf{i}\right]>\mathbf{A}\left[\mathbf{j}\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 $\mathbf{O}(\mathbf{nlog}\mathbf{n})$ time. (Hint: Split the array $\mathbf{A}$ into two arrays ${\mathbf{A}}_{\mathbf{1}}$and ${\mathit{A}}_{\mathbf{2}}$of half the size. Does knowing the majority elements of ${\mathbf{A}}_{\mathbf{1}}$and ${\mathbf{A}}_{\mathbf{2}}$help you figure out the majority element of ${\mathbf{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 ${\mathbf{A}}_{}$ arbitrarily, to get $\mathbf{n}\mathbf{/}\mathbf{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 $\mathit{n}\mathbf{/}\mathbf{2}$ elements left, and that they have a majority element if ${\mathbf{A}}_{}$ does.)

Short answer

1. It has been shown that the problem is solve in the given time $\mathrm{O}\left(\mathrm{nlogn}\right)$.
2. Linear Time algorithm is proposed with run time $\mathrm{O}\left(\mathrm{nlogn}\right)$.

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 $\mathrm{n}/2$.
• Name the first array ${\mathrm{A}}_1$and the second array.
• Take this same majority component from. and call it ${\mathrm{m}}_1$, then take the majority component from $A_2$.
• Determine if the number for $m_1$or $m_2$ is more than the array role="math" localid="1659779390830" $A\text{'}s$size.

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

function$\mathrm{majority}\left(\mathrm{s}[1,\dots ,\mathrm{m}]\right)$

Input: an array of numbers$\mathrm{s}[1,\dots ,\mathrm{m}]$

Output: majority value of array $\mathrm{S}$

$\mathrm{if}(\mathrm{m}==1)$

return$\left(\mathrm{s}\left[1\right]\right)$

$\mathrm{mid}=[\mathrm{m}/2]$

$\mathrm{l}\_\mathrm{elem}=\mathrm{majority}\left(\mathrm{s}[1,\dots ,\mathrm{mid}]\right)$

$\mathrm{r}\_\mathrm{elem}=\mathrm{majority}\left(\mathrm{s}[\mathrm{mid}+1,\dots ,\mathrm{m}]\right)$

if:$(\mathrm{l}\_\mathrm{elem}==\mathrm{r}\_\mathrm{elem})$

return$l\_elem$

$l\_sum=frequency(s[1,\dots ,m],l\_elem)$

$\mathrm{r}\_\mathrm{sum}=\mathrm{frequency}(\mathrm{s}[1,\dots ,\mathrm{m}],\mathrm{r}\_\mathrm{elem})$

if:$\mathrm{l}\_\mathrm{sum}>\mathrm{mid}+1$

return$\mathrm{l}\_\mathrm{elem}$

else if:$\mathrm{r}\_\mathrm{sum}>\mathrm{mid}+1$

return$r\_elem$

else

return $no-majority-elements$

Algorithm to find the frequency of the algorithm:

function$\mathrm{frequency}(\mathrm{s}[1,\dots ,\mathrm{m}],\mathrm{elem})$

Input: an array of numbers$\mathrm{s}[1,\dots ,\mathrm{m}]$

Output: count of element$elem$of the array$S$

for:$\mathrm{i}=1\mathrm{to}\mathrm{m}$

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

$inccount$

return$count$

Explanation:

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

• It returns$s\left[1\right]$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,\mathrm{...},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,\mathrm{...},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\left(n\right)$to count the majority element.

The recurrence relation is shown below:

$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}{b}\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$\mathrm{c}={\log }_{\mathrm{b}}\mathrm{a}$, then the running time is,

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{O}\left({\mathrm{n}}^{\mathrm{c}}\mathrm{logn}\right)$ …… (3)

Check if$\mathrm{c}={\log }_{\mathrm{b}}\mathrm{a}$ :

${\log }_{b}a$…… (4)

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

${\log }_{b}a={\log }_{2}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}{c}T\left(n\right)=O\left(n^1\text{logn}\right)\\ =O\left(n\log n\right)\end{array}$

Therefore, the algorithm takes a run time of $\mathrm{O}\left(\mathrm{n}\mathrm{logn}\right)$ .

Solution of part (b)

Solving the problem in linear time:

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

• Let $A_1$be the first array and $A_2$be the second array.

• Take the majority element from $A_1$ and call it ${\mathrm{m}}_1$, and take the majority element from $A_2$ and call it $m_2$.

• Determine whether the count of $m_1$or $m_2$ is more than the array $A$ size.

Linear time algorithm to find the majority of the element:

function$\mathrm{majority}\_\mathrm{linear}\left(\mathrm{s}[1,\dots ,\mathrm{m}]\right)$

Input: an array of numbers$s[1,\dots ,m]$

Output: majority value of array$s$

if$(m==2)$

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

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

else

return$no-majority-elements$

create array$temp\_array$

for :$\mathrm{k}=1\mathrm{to}\mathrm{m}$

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

Insert $\mathrm{s}\left[\mathrm{k}\right]$ into temp

$K=k+1$

return $\mathrm{majority}\_\mathrm{linear}\left(\mathrm{temp}\right)$

Algorithm for search of the theory of algorithm:

Function$\mathrm{frequency}\_\mathrm{linear}\left(\mathrm{s}[1,\dots ,\mathrm{m}]\right)$

Input: an array of numbers$s[1,\dots ,\mathrm{m}]$

Output: majority element of the array $\mathrm{S}$

$\mathrm{q}=\mathrm{majority}\_\mathrm{linear}\left(\mathrm{s}[1,\dots ,\mathrm{m}]\right)$

$\mathrm{count}=\mathrm{frequency}(\mathrm{s}[1,\dots ,\mathrm{m}],\mathrm{q})$

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

return$q$

else

return $\mathrm{no}-\mathrm{majority}-\mathrm{elements}$

Explanation:

• The function "majority linear" receives the array "$\mathrm{s}[1,\dots ,\mathrm{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$\mathrm{s}\left[1\right]$. 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\left(n\right)$.
  • "frequency linear" is a method that finds the majority of an element using the array "$s[1,\dots ,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\left(n\right)$.

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

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

Consider the master theorem for the following recurrence equation,

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{aT}(\mathrm{n}/\mathrm{b})+\mathrm{O}\left({\mathrm{n}}^{\mathrm{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$\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$ :

${\log }_{b}a$ …… (4)

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

${\log }_{\mathrm{b}}\mathrm{a}={\log }_{2}1=0$

$lo{g}_{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}{c}T\left(n\right)=O\left(n^1\right)\\ =O\left(n\right)\end{array}$

Therefore, the algorithm takes a run time of $O\left(nlogn\right).$