Best, average and worst case

Complexity analysis Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

Quick-select style pivoting on sorted input with the first item as pivot. What does this print?

Python 3.13
def comparisons(xs: list[int]) -> int:
    if len(xs) <= 1:
        return 0
    pivot, rest = xs[0], xs[1:]
    left = [x for x in rest if x < pivot]
    right = [x for x in rest if x >= pivot]
    return len(rest) + comparisons(left) + comparisons(right)

print(comparisons(list(range(20))))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 190

Right: sorted input makes every split lopsided, giving 19 + 18 + … + 1.

Choosing the first item as pivot on sorted input is the worst case, which is why real quicksorts pick pivots more carefully.

Why not the others?
  • B about 86. That is roughly n log₂ n, the cost with balanced splits.
  • C 20. Each level compares every remaining item against the pivot.

30-second answer

Worst case is the most work over all inputs of size n; average case is the expected work over some distribution of inputs; best case is the least. Quote the worst case by default, and add the average when it differs a lot: quicksort is O(n log n) on average but O(n²) in the worst case, and hash lookups are O(1) on average but O(n) when every key collides.

Practise saying it · 45 s. No recording, just a timer

Explain best, average and worst case.

Say your answer out loud, then check which of these points you covered:

  • Default to worst case
  • Mention average when different
  • Quicksort and hashing examples

Deep dive

Best case is rarely useful: almost any algorithm is fast on some lucky input.

Randomisation (random pivots, random hash seeds) makes the bad cases unlikely rather than impossible.

Python randomises string hashing per process, which protects dicts from crafted collisions.

Common mistakes

  • Quoting the best case as the complexity.
  • Calling quicksort O(n log n) without the worst-case caveat.

Senior take & follow-ups

Say 'worst case O(…), average O(…)' when they differ; it shows precision.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why is Python's sort not quicksort?

    Show hint

    It is Timsort-based: stable and O(n log n) in the worst case.

  2. When does the worst case matter most?

    Show hint

    When inputs can be chosen by an attacker, or latency limits are strict.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.