CODEWITHSUNDEEP
algorithmprobability
Colab Google
Colab Google

Reputation: 49

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

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?

Upvotes: 4

Views: 141

Answers (2)

cerveau70
cerveau70

Reputation: 59

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

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

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

Upvotes: 4

Stef
Stef

Reputation: 15525

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

INORDER ALGORITHM:
    i = 1
    while a[i] != 1:
        i += 1
    return i

The main difference between the random algorithm and the inorder algorithm is that the time of execution of the inorder algorithm depends strongly on the array you're given, whereas the time of execution of the random algorithm depends only on the luck of the random trials.

So the random algorithm is more "robust" because it won't become slower if you suddenly find yourself in a situation where all your arrays have been sorted and have 0s in their first half and 1s in their second half.

If you knew for sure that the array has been shuffled uniformly at random, then the two algorithms would be equivalent, but without that strong assumption, then the random algorithm is preferable for this reason.

Also, you should be careful with definitions. There are two factors that will impact the time of execution of your algorithms: the order of the input array, and the luck of the random trials. I think most complexity-theorists would argue that "best-case" and "worst-case" are meant with respect to the input array, not with your luck in the random trials. The complexity of the random algorithm is a random variable that follows a geometric distribution. It does not depend on the input array, therefore it has the same worst-case and best-case complexity, O(1), whereas the inorder algorithm has best-case complexity O(1) but worst-case complexity O(n).

Upvotes: 1

Related Questions