Analyzing Algorithm Complexities: Best, Average, and Worst Cases

1. What Are Best, Worst, and Average Cases?

An algorithm's runtime isn't always a single, fixed formula. It often depends on the properties of the input data. For an array of size $n$, some inputs might be "easy" for the algorithm, while others might be "hard."

Let's define these three levels of analysis:

• Best-Case Complexity: This is the performance of the algorithm on the "easiest" possible input of size $n$. It represents the minimum number of operations the algorithm will ever perform for a given input size. While interesting, it's rarely used for practical guarantees because we can't assume we'll always be lucky.

• Worst-Case Complexity: This is the performance on the "hardest" possible input of size $n$. It represents the maximum number of operations and provides a crucial guarantee: the algorithm will never perform slower than its worst-case bound. This is why it's the most common type of analysis you'll encounter.

• Average-Case Complexity: This describes the algorithm's expected performance averaged over all possible inputs of size $n$. This can be the most realistic measure, but it's often mathematically complex to calculate because it requires making assumptions about the statistical distribution of the inputs.

2. A Crucial Clarification: Cases vs. Notations

A common point of confusion is equating Big O with the worst case and Big Omega with the best case. This is incorrect.

• Cases (Best, Worst, Average) are types of analysis that result in a runtime function, e.g., $f(n)=n$ for the worst case of linear search.
• Notations ($O,\Omega ,\Theta$) are the mathematical tools used to describe the growth rate of that resulting function.

You can, therefore, describe the complexity of any case using any of the notations, although a tight ($\Theta$) bound is always the most descriptive.

• The worst-case complexity of linear search is $\Theta (n)$. It is also $O(n)$ and $\Omega (n)$.
• The best-case complexity of linear search is $\Theta (1)$. It is also $O(1)$ and $\Omega (1)$.

The following video explains this distinction exceptionally well. Understanding this point is key to mastering complexity analysis.

3. Case Study: Searching Algorithms

Let's see how this works with two fundamental search algorithms.

Linear Search

In a linear search, we iterate through an array one element at a time until we find our target.

• Best Case: The target is the very first element. We perform one comparison. The complexity is $\Theta (1)$.
• Worst Case: The target is the last element, or it's not in the array at all. We must perform $n$ comparisons. The complexity is $\Theta (n)$.
• Average Case: Assuming the target is equally likely to be at any position, the average number of comparisons will be $(1+2+...+n)/n=(n+1)/2$. Asymptotically, this is $\Theta (n)$.

The following video provides a detailed calculation for the average case of linear search.

Binary Search

Binary search works on a sorted array by repeatedly dividing the search interval in half.

• Best Case: The target is the middle element of the array. We find it in one comparison. The complexity is $\Theta (1)$.
• Worst Case: The target is not in the array, or we find it only when the search interval has been reduced to a single element. At each step, we halve the problem size. The number of times we can halve $n$ until we reach 1 is ${\log }_{2}n$. The complexity is $\Theta (\log n)$.
• Average Case: Similar to the worst case, most searches will require traversing deep into the "search tree," making the average complexity also $\Theta (\log n)$.

4. Case Study: Sorting Algorithms

Sorting algorithms provide some of the most classic examples of varying complexities.

Merge Sort

Merge sort is a divide-and-conquer algorithm that consistently splits the array in half, recursively sorts the halves, and then merges them back together.

• Best, Average, and Worst Case: The sequence of operations (divide, recurse, merge) is the same regardless of the initial order of the elements. It always performs the same number of divisions and the merge operation's cost depends only on the size of the subarrays, not their content. Therefore, all cases have a complexity of $\Theta (n\log n)$.

Quick Sort

Quick sort is another divide-and-conquer algorithm, but its performance is highly dependent on the choice of the "pivot" element used to partition the array.

• Best and Average Case: If the pivot is chosen well (near the median), the array is partitioned into two roughly equal halves. This leads to a balanced recursion tree and a complexity of $\Theta (n\log n)$.
• Worst Case: If the pivot is chosen poorly (e.g., always the smallest or largest element), the array is partitioned into a subarray of size 0 and a subarray of size $n-1$. This leads to a completely unbalanced recursion, essentially degrading to a slow, quadratic sort. This famously happens if you apply a naive Quick Sort to an already sorted array. The complexity becomes $\Theta (n^2)$.

Your experience with system performance tuning has likely given you an appreciation for how seemingly small implementation details can lead to drastically different outcomes. The difference between Quick Sort's $\Theta (n\log n)$ average case and its $\Theta (n^2)$ worst case is a prime example of this principle in algorithmics.

To see the analysis for these sorting algorithms, please review the relevant sections in the following resource.

Summary of Common Complexities

Here is a summary table for the algorithms we've discussed. This is a high-value reference for interviews.

Conclusion

You've now added a critical dimension to your analytical toolkit. You understand that an algorithm's efficiency isn't a single number but a profile that can change with the input.

Key Takeaways:

• Best, Worst, and Average cases describe an algorithm's performance under different input scenarios for a fixed size $n$.
• Worst-case analysis ($O$) is the most common because it provides a reliable performance guarantee.
• Asymptotic notations ($O,\Omega ,\Theta$) are used to describe the growth rate of the function derived from a case analysis; they are not the cases themselves.
• Algorithms like Quick Sort have different complexities for different cases, making them powerful but sensitive to input.
• Algorithms like Merge Sort have consistent performance across all cases, making them highly predictable.

In this lesson, we encountered recurrence relations for algorithms like Merge Sort and Quick Sort (e.g., $T(n)=2T(n/2)+O(n)$). In the next lesson, we will learn about the Master Theorem, a powerful "cheat code" that allows you to solve many common divide-and-conquer recurrences instantly, without having to unroll them manually.