Best, Average, and Worst Case Analysis — A Practical Guide for Every Algorithm

Introduction

When we say an algorithm is O(n log n), we are almost always referring to its worst case performance. But the worst case is only one part of the story. Real programs run on real inputs — and real inputs are not always the worst case.

Understanding the three cases of algorithm analysis — best case, average case, and worst case — allows you to:

• Choose the right algorithm for your specific data distribution
• Understand why certain algorithms outperform others on real-world data
• Make informed decisions about when to use worst-case-optimal algorithms vs. average-case-optimal ones
• Answer interview questions with depth and precision

This lesson explores all three cases in detail, with complete worked examples for major algorithms.

Analysis of Key Algorithms

Algorithm 1 — Linear Search

Code:

Identifying the three cases:

Best Case: The algorithm terminates as early as possible — when the target is found at the very first position.

Worst Case: The algorithm must examine every element — either the target is not present, or it is in the last position.

Average Case: Assuming the target is equally likely to be at any position (or absent):

Let p = probability the target is present = 0.5 (a common assumption)

Summary:

Algorithm 2 — Binary Search

Code:

Best Case: The target is the middle element of the array — found on the first comparison.

Worst Case: The target is not present, and the search reduces the array to a single element before failing.

Average Case: Expected number of comparisons when target is uniformly distributed:

For a sorted array of n elements, the average number of comparisons is approximately log₂(n) - 1.

This is because in a balanced binary search tree, the average depth of a node is log n - O(1).

Average case: Θ(log n)

Summary:

Important observation: Binary Search's best case is O(1) but its worst and average cases are Θ(log n). This is different from Linear Search, which has O(1) best but O(n) worst and Θ(n) average.

Algorithm 3 — Bubble Sort

Code:

Best Case: The array is already sorted. The first pass finds no swaps and terminates immediately.

Note: Without the swapped optimization, Bubble Sort is always O(n²) even for sorted input. The optimization is what creates the Ω(n) best case.

Worst Case: The array is reverse sorted. Every element must bubble to its correct position.

Average Case: For random permutations, on average n(n-1)/4 swaps are needed.

Average case: Θ(n²)

Summary:

Algorithm 4 — Insertion Sort

Insertion Sort is arguably the most interesting example because the difference between its best and worst cases is dramatic — and understanding this difference explains a key design decision in Python's built-in sorting algorithm.

Code:

Best Case — Already Sorted Input:

Worst Case — Reverse Sorted Input:

Average Case: For random input, each element has to shift past approximately half the sorted portion on average.

Expected shifts for element at position i ≈ i/2

Total expected shifts = Σ i/2 from i=1 to n-1 = n(n-1)/4

Average case: Θ(n²)

Why This Matters — TimSort:

Python's built-in sorted() and list.sort() use TimSort, a hybrid algorithm created by Tim Peters. TimSort runs on the key insight that:

• Real-world data often contains runs — subsequences that are already sorted (or nearly sorted)
• Insertion Sort's Ω(n) best case makes it ideal for processing already-sorted runs
• Merge Sort is used to merge the sorted runs efficiently

By splitting the data into runs and applying Insertion Sort to small/sorted portions, TimSort achieves near-O(n) performance on nearly sorted data while maintaining O(n log n) worst case.

Summary:

Algorithm 5 — Quick Sort

Quick Sort's three cases have the most dramatic spread of any common algorithm. Understanding them is essential for any serious programmer.

Code:

Best Case — Balanced Partitions:

The pivot always splits the array into two equal halves.

Worst Case — Worst Pivot Selection:

The pivot is always the smallest or largest element, creating maximally unbalanced partitions.

This is why choosing "last element as pivot" on an already-sorted array is disastrous.

Fix — Randomized Quick Sort:

By choosing a random pivot, the worst case remains O(n²) in theory (you could be unlucky every time), but the probability of this occurring becomes astronomically small.

Average Case:

For random pivot selection (or random input):

The expected number of comparisons is approximately 2n ln(n) ≈ 1.39 × n log₂(n).

Average case: Θ(n log n)

Summary:

Why Use Quick Sort Despite O(n²) Worst Case?

1. Average case is Θ(n log n) — same as Merge Sort
2. Better constant factors than Merge Sort (no auxiliary array copying)
3. Better cache performance (accesses contiguous memory)
4. Randomized version makes worst case practically impossible
5. In practice, Quick Sort runs faster than Merge Sort for most inputs

This is why C++, Java, and Python all use Quick Sort variants (often hybrid) for general-purpose sorting.

Algorithm 6 — Merge Sort

Merge Sort is the "safe" choice because its three cases are all the same.

Best Case: Θ(n log n) Average Case: Θ(n log n) Worst Case: O(n log n)

All cases: Θ(n log n)

Merge Sort always divides the array in half (creating log n levels) and always merges (doing n work per level). There is no short circuit, no early termination, no lucky input. It always does the same amount of work.

This predictability makes Merge Sort the choice when you need guaranteed performance.

Comparing Algorithms by Case

Choosing an Algorithm Based on Case Analysis

Summary

• Worst case (Big O): The maximum operations for any input of size n. Always the primary concern for safety guarantees.
• Best case (Big Omega): The minimum operations for the most favorable input. Useful for identifying optimization opportunities and understanding hybrid algorithms.
• Average case (Big Theta): Expected operations over all inputs. Most relevant for practical performance estimation.
• The gap between best and worst case reveals opportunities: large gaps (like Insertion Sort's Ω(n) vs. O(n²)) suggest the algorithm adapts to input structure — a feature that hybrid algorithms exploit.
• Always ask: "Is my real-world input closer to the best case or worst case?" This determines which algorithm is appropriate.

*Next Lesson: Space Complexity — Analyzing memory usage with the same rigor we have applied to time complexity.*