Best, Average, and Worst Case Analysis

Every algorithm behaves differently depending on the data you feed it. Best, average, and worst case analysis is how computer scientists describe that range of behavior precisely, instead of just saying an algorithm is “fast” or “slow.” Once you can reason about all three cases, you can predict how code will actually perform in production — not just on the friendly examples in a tutorial — and you can make informed tradeoffs between algorithms that all “work” but behave very differently under pressure.

Overview: What “Case” Means in Algorithm Analysis

Imagine searching a stack of ten unsorted resumes for a specific candidate’s name. If that candidate happens to be on top, you find them after checking one resume — that is the best case. If they are at the bottom, or not in the stack at all, you have to check all ten — that is the worst case. If you ran this search many times with the name in a random position, you would check about five resumes on average — the average case. The algorithm (checking resumes one by one) never changes; only the input’s arrangement changes how much work it takes.

This distinction matters because a single Big-O label can be misleading if you do not say which case it describes. Quicksort is a classic example: it is often quoted as O(n log n), and that is true for its best and average case, but its worst case is O(n^2) on certain inputs (as you will see traced below). Interviewers and production engineers care about all three, because the case that shows up depends entirely on the data you actually receive.

Big-O, Big-Omega, and Big-Theta

Formally, computer scientists use different notation for different bounds: O (Big-O) describes an upper bound (this algorithm never does more than this much work), Ω (Big-Omega) describes a lower bound (it never does less), and Θ (Big-Theta) describes a tight bound where the upper and lower bounds match. In everyday practice — including this site and most interviews — people use “Big-O” loosely to describe whichever case (best, average, or worst) is under discussion, and simply say “the worst-case time complexity is O(n^2)” rather than switching notation. Knowing the formal distinction helps you understand papers and textbooks, but the practical skill is asking “which case are we talking about?” every time you see a complexity claim.

Time and Space Complexity

The table below summarizes the operations used in this lesson’s examples. Notice how some structures have identical best, average, and worst case behavior (binary search), while others vary dramatically depending on the input (quicksort, list membership).

Operation Best Case Average Case Worst Case Space
Linear search O(1) O(n) O(n) O(1)
Binary search (iterative) O(1) O(log n) O(log n) O(1)
Quicksort (fixed first-element pivot) O(n log n) O(n log n) O(n^2) O(log n) avg, O(n) worst
Insertion sort O(n) O(n^2) O(n^2) O(1)
List membership (x in list) O(1) O(n) O(n) O(1)
Set/dict membership (x in set) O(1) O(1) O(n) O(n)

A few of these deserve justification. Binary search’s best and average case are both bounded by O(log n) because every comparison eliminates half the remaining search space regardless of where the target sits — the only way to beat that is an immediate hit at the first midpoint (the best case, O(1)). Quicksort’s worst case of O(n^2) happens when the chosen pivot is always the smallest or largest remaining element, which produces one partition of size n-1 and one of size 0 at every level of recursion — that gives n + (n-1) + (n-2) + … + 1 total comparisons, which sums to O(n^2). Quicksort’s recursion depth (space) follows the same logic: balanced partitions give a shallow O(log n) call stack, but the fully unbalanced worst case produces a call stack n frames deep, i.e. O(n) space. Set and dict membership are O(1) on average because hashing maps a key directly to a bucket, but degrade to O(n) in the worst case if many keys collide into the same bucket (rare in practice, but it is why hash-based structures are never a guaranteed O(1), only an average-case one).

Examples

Example 1: Linear Search — Best vs. Worst Case

def linear_search(arr: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    for index, value in enumerate(arr):
        comparisons += 1
        if value == target:
            return index, comparisons
    return -1, comparisons

data = [4, 2, 9, 7, 5, 1, 8, 3, 6, 0]

best_index, best_comparisons = linear_search(data, 4)
print(f"Best case: found at index {best_index} after {best_comparisons} comparisons")

worst_index, worst_comparisons = linear_search(data, 0)
print(f"Worst case: found at index {worst_index} after {worst_comparisons} comparisons")

missing_index, missing_comparisons = linear_search(data, 99)
print(f"Missing case: found at index {missing_index} after {missing_comparisons} comparisons")

Output:

Best case: found at index 0 after 1 comparisons
Worst case: found at index 9 after 10 comparisons
Missing case: found at index -1 after 10 comparisons

The target 4 sits at index 0, so linear_search returns after a single comparison — the best case, O(1). The target 0 sits at the very last index (9), so the loop must check all ten elements before matching — the worst case, O(n). Searching for 99, which is not present at all, forces the same full scan and also lands in O(n) territory: “not found” is just as expensive as “found at the end,” which is a detail people often forget when reasoning about worst case.

Example 2: Quicksort — Why Input Order Changes the Case

def quicksort_count(arr: list[int]) -> tuple[list[int], int]:
    comparisons = 0

    def sort(items: list[int]) -> list[int]:
        nonlocal comparisons
        if len(items) <= 1:
            return items
        pivot = items[0]
        less = []
        equal = []
        greater = []
        for item in items:
            comparisons += 1
            if item < pivot:
                less.append(item)
            elif item > pivot:
                greater.append(item)
            else:
                equal.append(item)
        return sort(less) + equal + sort(greater)

    return sort(arr), comparisons

sorted_input = [1, 2, 3, 4, 5, 6, 7, 8]
result_sorted, comparisons_sorted = quicksort_count(sorted_input)
print(f"Already-sorted input: {comparisons_sorted} comparisons")

shuffled_input = [5, 2, 7, 1, 8, 3, 6, 4]
result_shuffled, comparisons_shuffled = quicksort_count(shuffled_input)
print(f"Shuffled input: {comparisons_shuffled} comparisons")

Output:

Already-sorted input: 35 comparisons
Shuffled input: 17 comparisons

Both inputs have exactly 8 elements, yet the already-sorted list takes more than twice as many comparisons as the shuffled one. This implementation always picks items[0] as the pivot. On the sorted input, the pivot is always the smallest remaining value, so every partition splits into an empty “less” side and an (n-1)-sized “greater” side — the maximally unbalanced case that produces 8 + 7 + 6 + 5 + 4 + 3 + 2 = 35 comparisons, matching the O(n^2) worst case. On the shuffled input, the pivot happens to split the remaining items into more balanced groups at each step, producing only 17 comparisons — much closer to the O(n log n) average case. Same algorithm, same input size, very different case.

Example 3: Binary Search — Best, Average, and Worst in One Run

def binary_search(arr: list[int], target: int) -> tuple[int, int]:
    left, right = 0, len(arr) - 1
    comparisons = 0
    while left <= right:
        comparisons += 1
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid, comparisons
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1, comparisons

sorted_data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

best_index, best_comparisons = binary_search(sorted_data, 9)
print(f"Best case: found 9 at index {best_index} in {best_comparisons} comparison(s)")

average_index, average_comparisons = binary_search(sorted_data, 3)
print(f"Average case: found 3 at index {average_index} in {average_comparisons} comparison(s)")

worst_index, worst_comparisons = binary_search(sorted_data, 20)
print(f"Worst case: 20 not found (index {worst_index}) after {worst_comparisons} comparisons")

Output:

Best case: found 9 at index 4 in 1 comparison(s)
Average case: found 3 at index 1 in 2 comparison(s)
Worst case: 20 not found (index -1) after 4 comparisons

Searching for 9 matches on the very first midpoint (index 4), giving the best case of a single comparison. Searching for 3 takes two comparisons: the first midpoint (9) is too high, narrowing the search to the left half, where the second midpoint immediately matches. Searching for 20, which is larger than every element, forces the search window to shrink all the way down before left finally exceeds right — four comparisons, the worst case for this array of 10 elements, consistent with O(log n) (log2(10) ≈ 3.3, rounding up to 4 comparisons including the final exhausted check).

How It Works Step by Step

Let’s trace the worst-case binary search call, binary_search(sorted_data, 20), one iteration at a time, watching how left and right narrow the search window:

Step left right mid arr[mid] Action
1 0 9 4 9 9 < 20, so left = mid + 1 = 5
2 5 9 7 15 15 < 20, so left = mid + 1 = 8
3 8 9 8 17 17 < 20, so left = mid + 1 = 9
4 9 9 9 19 19 < 20, so left = mid + 1 = 10
— 10 9 — — left <= right is now false (10 <= 9); loop ends, return -1

Each step halves the remaining window ([left, right]), which is exactly why the number of steps grows with log2(n) rather than n: starting from 10 elements, the window shrinks to roughly 5, then 2, then 1, then 0 remaining candidates. This halving is only valid because the array is sorted — if sorted_data were unsorted, discarding half the array based on one comparison could just as easily discard the target, which is why binary search has a hard prerequisite that linear search does not.

Common Mistakes

Mistake 1: Using a list for repeated membership checks

It is tempting to check membership with plain lists, but x in list is O(n) in the worst case, so doing it inside a loop silently creates an O(n × m) algorithm:

def find_common_items(list_a: list[int], list_b: list[int]) -> list[int]:
    common = []
    for item in list_a:
        if item in list_b:  # O(n) scan of list_b on every iteration
            common.append(item)
    return common

list_a = [1, 2, 3, 4, 5]
list_b = [4, 5, 6, 7, 8]
print(find_common_items(list_a, list_b))

Output:

[4, 5]

This produces the right answer, but for larger inputs it re-scans list_b from scratch for every item in list_a. Converting list_b to a set once turns each membership check into an O(1)-average operation, dropping the overall complexity to O(n + m):

def find_common_items_fast(list_a: list[int], list_b: list[int]) -> list[int]:
    set_b = set(list_b)
    return [item for item in list_a if item in set_b]

list_a = [1, 2, 3, 4, 5]
list_b = [4, 5, 6, 7, 8]
print(find_common_items_fast(list_a, list_b))

Output:

[4, 5]

Mistake 2: An off-by-one that turns the worst case into an infinite loop

Analyzing worst-case behavior is exactly when subtle bugs surface, because the worst case is often the path that exercises the most iterations. Here is a broken binary search where a copy-paste slip forgets to advance left past mid:

def buggy_binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid  # bug: should be mid + 1, so left never advances past mid
        else:
            right = mid - 1
    return -1

On a small array searching for a present value this can still terminate, but on the worst-case path — searching for a value larger than every element — mid can stall at the same value repeatedly (integer division rounds down, so when left and right are adjacent, mid equals left forever), and the loop never exits. This is precisely why worst-case analysis matters for correctness, not just speed: a bug that never shows up on friendly inputs can hang production on an adversarial one. The fix is one character:

left, right = 0, len(arr) - 1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
return -1

Mistake 3: Picking a pivot that guarantees the worst case

Example 2 showed that a first-element pivot degrades to O(n^2) on already-sorted (or reverse-sorted) input:

pivot = items[0]
less = [item for item in items if item < pivot]
equal = [item for item in items if item == pivot]
greater = [item for item in items if item > pivot]
return quicksort(less) + equal + quicksort(greater)

Sorted or reverse-sorted data is common in real systems (timestamps, already-processed batches, IDs), so this is not a rare edge case — it is a predictable trap. Picking the middle element (or, better, a randomized element) as the pivot makes it far less likely that ordinary, non-adversarial input triggers the unbalanced worst case:

mid_index = len(items) // 2
pivot = items[mid_index]
less = [item for item in items if item < pivot]
equal = [item for item in items if item == pivot]
greater = [item for item in items if item > pivot]
return quicksort(less) + equal + quicksort(greater)

Best Practices

  • Always state which case a Big-O claim describes — “quicksort is O(n log n)” is only true for its average and best case; its worst case is O(n^2).
  • In interviews, default to discussing worst-case complexity unless the interviewer asks about average case specifically — worst case is a guarantee, average case is a statistical claim about typical inputs.
  • Do not choose an algorithm based on best-case behavior when input can be adversarial or attacker-controlled (e.g., a public API accepting arbitrary arrays); prefer structures with a well-bounded worst case, like merge sort (O(n log n) guaranteed) over naive quicksort.
  • Randomize pivot selection (or use median-of-three) in quicksort implementations so that common inputs like sorted or reverse-sorted data do not reliably trigger the worst case.
  • Reach for a set or dict instead of a list whenever you need repeated membership tests — it changes an O(n) worst-case check into an O(1) average-case one.
  • Remember that “average case” is only meaningful relative to an assumed input distribution; if your real inputs do not match that assumption (e.g., mostly-sorted data feeding a sort expecting random order), measure against your actual data instead of trusting the textbook average.

Practice Exercises

  • Using the linear_search function from Example 1, predict what input and target would produce the best case (1 comparison) and what would produce the worst case (all elements checked) for a list of 20 elements. Then run the code to confirm your prediction.
  • Using quicksort_count from Example 2, hand-trace (or run) the function on the reverse-sorted input [8, 7, 6, 5, 4, 3, 2, 1]. Is the comparison count closer to the already-sorted case (35) or the shuffled case (17)? Explain why using the pivot-selection logic.
  • Interview-style: explain why binary search is O(log n) and not O(n), what property of the input this bound depends on, and what would happen (in terms of correctness, not just speed) if you ran binary_search on an unsorted array.

Summary

  • Best, average, and worst case describe how an algorithm’s running time varies across different arrangements of input data, not different input sizes.
  • A Big-O claim is incomplete without saying which case it refers to — quicksort is O(n log n) on average and in the best case, but O(n^2) in the worst case.
  • Linear search: O(1) best, O(n) average and worst. Binary search: O(1) best, O(log n) average and worst (requires sorted input). Quicksort with a naive pivot: O(n log n) best/average, O(n^2) worst.
  • List membership (x in list) is O(n); set/dict membership is O(1) on average because of hashing, but O(n) in a pathological worst case of hash collisions.
  • Worst-case bugs (like an infinite loop from an off-by-one) often hide behind inputs that never occur in casual testing — always test the worst-case path explicitly, not just the happy path.
  • Choose algorithms based on the case that matches your real-world risk: average case for typical throughput, worst case for guarantees you cannot afford to violate.