How to Analyze the Best, Average, and Worst-Case Performance of a Randomized Algorithm for Finding a Value in an Array?

Question

Consider the following algorithm:

while True:
     i = random(1, n)
     if a[i] == 1:
         return i

The objective is to find a position in an array 𝑎[1..n] that contains the value 1, where half of the values in 𝑎 are zeroes and the other half are ones. The function random(1, n) returns a random integer between 1 and 𝑛.

How can I calculate the best, average and worst-case performance of this algorithm?

Answer 1

1. Best Case (Optimal Scenario)

The best case occurs when the index chosen randomly on the first iteration corresponds to an index containing a 1.

The probability of success in the first iteration is: P(success on first try) = Number of elements equal to 1 / Total number of elements = (n/2) / n = 1/2.

The number of iterations in this case: 1.

Complexity: O(1).

2. Average Case (Expected Scenario)

In the average case, the number of trials required to find a position containing a 1 follows a geometric distribution. This is because each attempt is an independent trial with a success probability of 1/2.

The expected number of trials for a geometric distribution is: E(number of trials) = 1 / P(success) = 1 / (1/2) = 2.

On average, the algorithm requires 2 iterations to find a 1.

Average complexity: O(1).

3. Worst Case (Unfavorable Scenario)

The worst case happens when the algorithm repeatedly selects indices containing 0 before finally finding a 1. Theoretically, it could take an arbitrarily large number of iterations before success, as the process is probabilistic.

The probability of failing k-1 times and succeeding on the k-th trial is: P(success on k-th trial) = (1 - 1/2)^(k-1) * (1/2).

While the worst-case scenario is extremely rare, the number of iterations can grow arbitrarily large.

Worst-case complexity: unbounded (theoretically infinite).

Summary of Performances

Case	Number of Iterations	Complexity
Best Case	1	O(1)
Average Case	2	O(1)
Worst Case	Theoretically infinite	Unbounded