DS & A (Algorithm Analysis - Best, Worst and Average Case)

| CHAPTER 5 |

Note: If it's your first time visiting this website I strongly recommend you to read the previous chapter before reading this chapter.

Till now we learned about what Data Structures and Algorithms are, some basic terminologies and a few concepts of Algorithm analysis. And continuing our ongoing journey of Data Structures and Algorithms, today we will discuss the Best Case, Average Case and Worst Case of an algorithm.

Algorithm Case Analysis

In the last chapter, we learned that every algorithm has running time[T(n)] and a growth rate. But that's not the end of it, an algorithm's running time and growth rate are not the only factors that we should consider while designing an algorithm. For some algorithms, different inputs result in different running time. And that brings forth the necessity of the concept of Best, Average, and Worst Case of algorithms.

Example

Consider we have four boxes tagged 1,2,3 & 4, and the boxes contain a Bear, a Rabbit, an Elephant and a Cow respectively. 

Case 1:

What would we do if someone says us that there is a cow in one of the box and if we come up with an algorithm to find the cow we'll receive a million dollar( given that we don't know anything other than the fact that there is a cow in one of the box). Now, how should we proceed?

Animals & Boxes

Well, the obvious solution is to check all the boxes one by one (assuming that we don't end up becoming bear food... :P)

Now, if we look at the picture above we can see that the cow is in the fourth box so we have to open four boxes before finding the cow. If we were a computer then the cow would have been the input and, opening the boxes can be considered to be the basic operation. So, we have to repeat the basic operation four times before finding the cow, which can also be interpreted as,

T(n = cow) = 4C; (c being the constant time required to open a box)

Case 2:

But what if we were asked to find the rabbit, we will find it just after opening the second box which means input rabbit can be processed with just two repetitions. Again, that can be interpreted as,

T(n = rabbit) = 2C; (c being the constant time required to open a box)

conclusion

So, we can say from the above example that an algorithm's running time can actually change with the change in the input size. 

Extra Info: The above-mentioned algorithm to search for the desired value in a sequence by checking its availability in the sequence one by one is called Sequential Search.

And we can also conclude that we ain't getting any million dollars just by finding a cow... :P

Which case is ideal for Algorithm Analysis?

Now that we know for some algorithms running time is not consistent. So, how do we keep track of the running time of such algorithms? Well, we don't need to keep track of all the different running times of such algorithms. We only need to care about the Best, Average and Worst case.

Best Case

Best Case is the one that is the least important among the three in most cases. It is because considering the best case for an algorithm is too optimistic.

Consider, we are designing an algorithm for maintaining the city traffic. Let's say that the traffic algorithm is designed to work on data arranged in the order Car, Bike, SUV and then Truck. Try to imagine it as our Animal & Boxes example from above. So, we can think of the data for the truck to be in the fourth box as the cow and the data for the car to be in the first box as the bear.

(Car) 1         (Bike) 2          (SUV) 3          (Truck) 4

So, if the traffic is filled with cars the algorithm will undoubtedly work at it's best, i.e. T(n) = C, but the real problem starts if the majority of the traffic is truck, then the algorithms running time will become, T(n) = 4C. As we can see, considering the best case for analysis of this algorithm will end up putting the city traffic in chaos. So, the best case will be usually considered if and only if it's highly likely to occur.

Worst Case

Then, Is the worst case a better option? The best part about knowing the worst case is that we will know that the algorithm will at least work that well. The worst case is suitable only in cases like the above traffic algorithm example making the worst case the perfect candidate for real-time applications. 

Average Case

The Average case is the best candidate for our day to day general programming algorithms. It's the aggregate of the running time of an algorithm on many different inputs. So, we might say that we just found the ideal case to focus on while analyzing an algorithm, but that's not how simple it is. The average case is heavily dependent on the data distribution in a data structure. So, the average case analysis is not always possible(We will learn more about it in the upcoming chapters). 

Graphical representation of Best, Average and Worst Case

( If you like the content here, follow TSP on social media to get notified on future updates)