Algorithm Analysis: Best, Worst and Average Case

Algorithms are a sequence of decisions we make to solve a problem. Like every decision in life we can make great decisions and really terrible decisions. But it doesn’t end there. Good decisions vary, they can come easy and can take a lot harder process to reach an expected outcome. There are 3 categories of efficiency an algorithm can fall under when analyzing its usage of resources. They are best case, worst case, and average case.

To give you a mind picture, my friend Jesse and I decided to go on a road trip. We were to travel 300 miles and Jesse assured me we had enough gas for each gas station stops through the journey. Jesse made a good calculation but ignored the possibility of errors which led to an unexpected outcome when we had traveled 160 miles and found that the next gas station wasn’t functional. This was really unfortunate because the next gas station was 80 miles away and we were about to hit the E. We got it to 220 miles through our journey and the car stopped. We wanted to hitchhike through the rest of the journey but after waiting for 2 hours with no passerby we had to decide on walking down to the next gas station with some gallons we had in the car.

2 miles after the next gas station, there’s another station, and another one 1 mile after that. That’s a good reason to believe going to fetch some gas would be a better decision than waiting for hours for a chance to hitchhike. But another condition we were constrained by was that our car runs on diesel and while there’s always petrol in all gas stations, they don’t always have diesel.

So far we’ve chosen footslogging with gallons over hitchhiking. We think it’s a good decision but we have another case here. If the gas station 20 miles away has diesel, that’d be the best case, if we have to try the first and second second gas stations to find that only the third has diesel or none of them have diesel, it would be the worst case. If the second gas station has diesel and the first didn’t then we don’t have to try the third. That’s an average case.

With that understanding, when giving an array of length n, when n = 5 and our array items are 23, 34, 13, 44, 18, we are to write an algorithm to find a number in the list of array items. By performing a linear search, we will have our best case if 23 is the number to be searched as it is the first item on the array.

k = 23

$C_{best} (n) = 1$

If we then have to search for 18 or any other number like 58 which doesn’t exist in the list, it’d be a worst case efficiency.

$k = 18$

C_{worst} (n) = n

For every possibility of worst case either the item is found in the last position or not found at all we go through the n number of elements.

34, 13, and 44 are the average cases of the search. To find any of those items at a position i of the array, we derive the probability of success and failure. Given that:

Probability of Successful Search = p

$where, 0 \leq p \leq 1$

$Probability of Unsucessful Search = 1 - p$

The probability to find an item that is neither the first nor last item of the array at a position i in the array then becomes:

p / n

and the probability of reoccurence of the item in position i would be:

C_{average} (n) = [1 x \frac{p}{n} + 2 x \frac{p}{n} + \dots + i x \frac{p}{n} + \dots + n x \frac{p}{n}] + n (1 - p)

with 1 - p added as probability of unsuccesful search.

Simplifying the above equation we get:

\frac{p}{n} [1 + 2 + \dots + i + \dots n] + n (1 - p)

and substituting the series with $\frac{n (n + 1)}{2}$ , we have:

\frac{p}{n} [\frac{n (n + 1)}{2}] + n (1 - p) \frac{p (n + 1)}{2} + n (1 - p)

we have a simplified addition of successful search and unsuccessful search for an average case. The probability § of a successful search (certainty) is 1 and unsuccessful search (impossibility) is 0. To start with the successful search we substitute p for 1.

Successful Search \to \frac{1 (n + 1)}{2} + n (1 - 1) C_{average} (n) = \frac{(n + 1)}{2}

For unsuccessful search, p is substituted for 0:

Unsuccessful Search \to \frac{0 (n + 1)}{2} + n (1 - 0) C_{average} (n) = n

and the unsuccessful search of average case has led right back to being the same as worst case.

C_{unsuccessful average} (n) = C_{worst} (n)

The best case from the examples is the optimum solution to the problems while every other solutions are feasible. Feasible solutions are the set of input values that satisfy all the constraints of an algorithm. Hence, going to the first and second gas stations before finding diesel at the third still makes the first and second feasible solutions while the third becomes the optimum solution.

Algorithm Analysis: Best, Worst and Average Case

Newer post

Older post