Question

Suppose that the votes of $\mathit{n}$people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes.

a) Devise a divide-and-conquer algorithm that determines whether a candidate received a majority and, if so, determine who this candidate is. [Hint: Assume that $\mathit{n}$is even and split the sequence of votes into two sequences, each with $\mathit{n}\mathbf{/}\mathbf{2}$elements. Note that a candidate could not have received a majority of votes without receiving a majority of votes in at least one of the two halves.]

b) Use the master theorem to give a big-$\mathit{O}$estimate for the number of comparisons needed by the algorithm you devised in part (a).

Short answer

a) Our recursive calculation will take a grouping of names and decide if one name happens as additional than half of the components of the grouping, and assuming this is the case, which name that is. On the off chance that the succession has only one component, at that point the one individual on the rundown is the champ.

b)$O(n\log n)$

Step-by-step solution

Master Theorem definition

In MASTER THEOREM, let $\mathit{f}$be an increasing function that satisfies the recurrence relation$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathit{a}\mathit{f}\mathbf{(}\mathit{n}\mathbf{/}\mathit{b}\mathbf{)}\mathbf{+}\mathit{c}{\mathit{n}}^{\mathbf{d}}$whenever$\mathit{n}\mathbf{=}{\mathbf{8}}^{\mathbf{t}}$, where$\mathit{k}$is a positive integer,$\mathit{a}\mathbf{⩾}\mathbf{1}\mathbf{,}\mathit{b}$is an integer greater than$\mathbf{1}$, and$\mathit{c}$and$\mathit{d}$are real numbers with$\mathit{c}$positive and$\mathit{d}$nonnegative. Then$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is$\mathit{O}\left(n^d\right)$if$\mathit{a}\mathbf{<}{\mathit{b}}^{\mathbf{d}}\mathit{O}\left(n^{d}logn\right)$if$\mathit{a}\mathbf{=}{\mathit{b}}^{\mathbf{d}}$and$\mathit{O}\left(n^{lo{g}_{b}a}\right)$if$\mathit{a}\mathbf{>}{\mathit{b}}^{\mathbf{d}}$ .

Apply Master Theorem

a) Our recursive calculation will take a grouping of names and decide if one name happens as additional than half of the components of the grouping, and assuming this is the case, which name that is.

On the off chance that the succession has only one component, at that point the one individual on the rundown is the champ.

For the recursive stride, isolate the rundown into two sections the first half and the second half-as similarly as could reasonably be expected.

As is brought up in the clue, nobody could have gotten a dominant part of the votes on this rundown without having a lion's share in one half or the other, since if a hopeful got not exactly or equivalent to a large portion of the votes in every half, then he got not exatctly or equivlent to a large portion of the votes taking all things together.

Apply the calculation recursively to every half to think of at most two names.

At that point go through the whole rundown the check the of names to choose which, assuming either, is the champ.

This requires at most $2n$extra examinations for a rundown of length $n$.

b) We apply the ace hypothesis with $\text{a}=2,\text{b}=2,\text{c}=2$, and $d=1$. Since$\text{a}=b^d$ , we realize that the number of correlations is $\text{O(}{n}^{d}logn)=\text{O}(\text{n}\text{log}\text{n})$.