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).
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).
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 |