Complexity cases and how to use them

You already understand what each case means and have seen some examples of where they apply. This topic will teach you a crucial skill for algorithm developers: how to select an algorithm from possible options by analysing the best, average, and worst cases. To do this, you need to understand the advantages and drawbacks of examining each case. You also have to learn the type of information you get from each case. Let's get started!

Bias of Best Cases

Picture an automated system at a factory that deals with a specific data format. The system's program should be tailored to the data for top performance. For instance, if you only need to process every third column in the data, there's no need to check the others. A program optimised for certain data will demonstrate the best performance. However, another factory might not be able to use your program. Such a program is highly dependent on the data, making it difficult to adapt to different data.

Therefore, overall development and choice of algorithms are rarely based on the best-case performance. Developers never create an algorithm based on the best-case scenario so that the algorithm remains versatile and flexible.

Worst Case is Best for Analysis

Studying worst cases is handy for efficiency analysis as algorithms are usually compared based on worst cases. In terms of runtime, the worst-case time complexity equates to the longest running time required for an algorithm to finish, given any input of size $n$. It guarantees that the algorithm execution will not exceed the stated time. The growth order of the worst-case complexity, such as quadratic or logarithmic, is commonly used to compare the efficiency of two algorithms.

For example, you'll notice that the worst case of quicksort is much "worse" than the worst case of merge sort as it grows more rapidly.

When discussing an algorithm's time complexity, it specifically refers to the worst case. Therefore, when you hear "Bubblesort complexity is $O(n^2)$", it means the worst case of this algorithm.

Complexity of Studying Average Cases

You might initially think that studying average cases is pointless if you're looking at the worst. Working with the worst cases allows you to include a time margin. Also, assessments based on the worst case are guaranteed to be dependable and error-free. So, does the study of average cases by computer scientists mean it's necessary for everyone?

Yes, it does! There are three main reasons for studying average-case complexity:

1. The inputs that generate the worst case are uncommon, so the worst case might not be indicative;

2. Analysing average cases helps to develop optimal algorithms in various fields;

3. If the worst cases of two algorithms are similar, their average cases may vary, making the comparison of the average cases more illustrative.

Example

Okay, you understand the who, what, when, where, and why, but you still have to fully grasp the "how". In other words, you need a deeper understanding of how to decide between algorithms considering their best, average, and worst cases. Let's examine an example where you have to select a sorting algorithm. Suppose you want to sort a few of the first digits of $\pi = 3.1415926535897932384626433832795...$.

If we regard $\pi$ as an $[3,1,4,1,5,9,2,6,5,3,5,8,9]$ array, then almost every sorting algorithm will work because the array of $\pi$ digits isn't too large. But what if we consider many more digits? Below, you can see the algorithms and their calculated complexity cases:

Given a small but unsorted array, we can't consider it as the best case of a dataset. This means we can disregard the "Best case" column entirely. Now, let's look at the common sequence of the first digits of $\pi$. It makes sense to concentrate on the average cases of the sorting algorithms presented. Their time complexities are $O(n \cdot log\:n)$, $O(n^2)$, and $O(n \cdot n!)$. As the last two are worse than $O(n \cdot log \:n)$, you can confidently select either quick sort or merge sort.

But how do you make the final decision? For this, you also need to examine the worst case. What if you had to sort the first 10,000 digits of $\pi$? This isn't the worst case since there are more than 10,000 digits in $\pi$, but such a large array has to be accounted for. Therefore, you can conclude that the merge sort algorithm will be the best choice for your situation.

Conclusion

Identifying the best, average, and worst cases for an algorithm you're considering is mandatory, as the result will directly affect your program's efficiency. Normally, you don't need to consider the best case as the algorithm you choose to implement won't always have the same dataset as input. However, understanding the algorithm's upper limit is vital, as it ensures you can fit the algorithm's execution within a known limited time.

Analyzing average cases isn't pointless, even if you know the worst-case time complexity. Comparisons between two algorithms are more accurate when you know the average cases because it's rare for the worst cases to occur in practice. Thus, considering the average cases is more suitable for real-life scenarios and statistics.

Reviewing complexity cases is important for a variety of tasks like cryptography, sorting problems, data structures, and optimization. It's a central part of studying algorithms, and future topics related to specific algorithms will always include their complexity analysis.