Runtime of randomization algorithm to find majority element in an array?

Question

This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such a number by selecting a random index and checking if it's value is the majority element or not, and repeat until it's found. This is one of the solutions provided.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority_count = len(nums)//2

        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

What I'm confused about is the runtime analysis of this algorithm, which is based on the assertion that since the majority element is always guaranteed to occupy more than half of the array, this algorithm applied to our scenario will always be faster than if it were applied to the scenario where there existed only an element that occupied exactly half the array. Therefore the expected number of iterations EV_(itersprob) can be represented as being less than or equal to the expected number of iterations of the modified scenario EV_(itersmod)

What I'm confused about is how this series was put together for this problem. The variable i is the iteration number, but why are you summing for (i * (1/2^i))?

Basically the runtime for the number of iterations of the while loop is expected to be constant, making the runtime of this entire algorithm linear (due to the inner loop running n times each time)

Answer 1

$i$ is the number of tries, and $\frac{1}{2^i}$ is the probability of needing that many tries.

We can lay out all outcomes on the table, assign the probability of each outcome, and then sum them all up. So for example,

• The probability of needing only 1 try is 1/2
• The probability of needing 2 tries is 1/4
• The probability of needing 3 tries is 1/8

If you sum up the terms then you get $1\times\frac{1}{2} + 2\times\frac{1}{4} + 3\times\frac{1}{8} + ... n\times\frac{1}{2^n}$. The official formulation as $n$ approaches infinity thus becomes:

$$ \lim_{n \to \infty} \sum_{i=1}^{n} i\times\frac{1}{2^i} $$

---

Now we have, \begin{align} S_n &= 1\times\frac{1}{2} + 2\times\frac{1}{4} + 3\times\frac{1}{8} + \cdots + n\times\frac{1}{2^n} \\ S_n\times \frac{1}{2} &= \quad\quad\quad\quad 1\times\frac{1}{4} + 2\times\frac{1}{8} + \cdots + (n-1)\times\frac{1}{2^n} + n\times\frac{1}{2^{n+1}}\\ \hline S_n\times \frac{1}{2} &= \quad\frac{1}{2}\quad + \quad\frac{1}{4}\quad + \quad\frac{1}{8}\quad + \quad\cdots\quad + \quad\frac{1}{2^n}\quad - \quad n\times\frac{1}{2^{n+1}} \end{align} Thus, $S_n = \sum\limits_{i=1}^{n-1} 2^{-i} + \frac{n}{2^n} = \frac{1 - 2^{-n}}{1 - 1/2} + \frac{n}{2^n} = 2 + \frac{n-2}{2^n}$ and the sum converges to $2$.