Suppose that the votes of $n$ people for different candidates $\left(\text{ where there can be more than two candidates } \right)$ for a particular office are the elements of a sequence . A person wins the election if this person receives a majority of the votes.
Devise a divide and conquer algorithm that determines whether a candidate received a majority and , if so , determine who this candidate is.
My Approach --:
$\Rightarrow$ Divide the list into two half $\frac{n}{2}$ $\left ( \text{assuming } n=2^{k} \right)$
$\Rightarrow$ will last dividing list till we reach containg $2$ list .
$\Rightarrow$ we will have toscan for all $n$ element to find the occurance of the majority one .
So recurrence relation looks like
$T \left( n \right)$ = $2*T \left(\frac{n}{2} \right)$+$n$ = $2^{k}*T \left(\frac{n}{2^{k}} \right)$+$n$*$k$
Now terminating condition becmes when $T \left( \frac{n}{2^{k}} \right)$ = $1$
where $\frac{n}{2^{k}} $=$2$ $\Rightarrow 2^{k} =\frac{n}{2} $
Coming back to my equation , $T \left( n \right)$ = $2^{k}$+$n$*$k$ =$\frac{n}{2}$+n * $log_{2} \frac{n}{2}$
$\Theta \left(n \right)$=$n*log _{2} \frac{n}{2}$
am i correct ??..add some points where i am wrong ..thank you !