Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 225 · Analyzing Algorithms

Best, Worst and Average Case

Understand why one algorithm can have several running times. Compare best, worst and average case with linear search, insertion sort and quicksort pivots.

Ask "how long does linear search take?" and the honest answer is "it depends on the list". If the value you want is the first item, the search stops immediately. If it is last, or not there at all, the search walks the entire list. The same code, the same n, very different amounts of work.

Many algorithms behave like this: their cost depends not just on the size of the input but on its shape. To describe that fairly, we analyze three scenarios: the best case, the worst case and the average case. This lesson explains each, shows how to measure them by counting steps, and clears up a common confusion between "case" and "Big O / Ω / Θ".

Three cases, one algorithm

Consider linear search: scan a list from the left until you find the target.

  • Best case: the target is the first item. One comparison. O(1).
  • Worst case: the target is the last item or missing. n comparisons. O(n).
  • Average case: the cost averaged over all the inputs you expect. If the target is equally likely to be at any of n positions, the average is (n + 1) / 2 comparisons. That is still O(n).
TEXT
target at index:   0    1    2    3    4    ...   n-1    (missing)
comparisons:       1    2    3    4    5    ...    n        n

best = 1       worst = n       average (present) = (1 + 2 + ... + n) / n = (n + 1) / 2
Python Linear search: best, worst, average

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured average, 50.5, matches the formula exactly because we tried every target exactly once. That assumption (all positions equally likely) matters: if your data tends to have the wanted item near the front, the real average is lower.

What each case is for

Worst case is the one you will quote most often. It is a guarantee: no input, however unlucky, will take longer than this. It matters for real-time systems, security (attackers choose bad inputs on purpose) and any promise to users. When someone says "binary search is O(log n)", they mean the worst case.

Best case is usually the least useful. It describes an input that rarely happens. It is still worth knowing when an algorithm can finish early on friendly data, as with insertion sort below.

Average case describes typical behavior. To compute it you need an assumption about how inputs are distributed, which is also its weakness: the assumption may be wrong. The average gives an expected cost, a probability-weighted mean of the possible costs.

Best, worst and average are statements about which input you feed the algorithm. They are not the same thing as O (upper bound), Ω (lower bound) and Θ (tight bound), which describe how a function grows. You can give an O, Ω or Θ bound for any one of the three cases. "Worst case is Θ(n)" and "the best case is Ω(1)" are both fine sentences.

Input-sensitive algorithms: insertion sort

Insertion sort shows how dramatic input shape can be. It builds a sorted prefix, inserting each new item by shifting larger ones to the right. If the list is already sorted, nothing shifts. If the list is reversed, every item shifts past everything before it.

Python Insertion sort on three kinds of input

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the sorted list, each of the n − 1 insertions does one comparison and stops: O(n) best case. For the reversed list, the count is exactly n(n−1)/2: O(n²) worst case. The shuffled list lands in between, about half of the worst case, which is still O(n²). An algorithm like this is called adaptive: it runs faster when the input is closer to sorted. That is why hybrid sorts such as Timsort use insertion sort on small or nearly sorted runs (see Shell sort, Timsort and hybrids).

A case that depends on a choice: quicksort

Quick sort picks a pivot, splits the list into smaller and larger items, then recurses on both sides. If the pivot lands near the middle, the sizes halve each time and the cost is O(n log n). If the pivot is the smallest or largest item every time, one side is empty and the recursion goes n deep, costing O(n²).

TEXT
good pivot:   [ 3 1 4 | 5 | 9 2 6 ]   halves, depth ~ log n
bad pivot:    [   | 1 | 2 3 4 5 6 9 ] peels one item per level, depth ~ n

Here is a quicksort that counts comparisons and lets you choose how to pick the pivot:

Python Quicksort pivot rules on sorted input

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On sorted input the first-element rule does about n²/2 comparisons, because every pivot is the smallest remaining item. The middle rule is perfect on sorted data. The random rule is never fooled by a particular order: no input is "bad" for it, only unlucky random choices are, and those are rare. Real libraries use tricks like median-of-three or random pivots precisely to push the worst case out of reach.

Notice how the answer to "what is the complexity of quicksort?" depends on the pivot rule: O(n log n) average, O(n²) worst case with a naive pivot. Saying both is the correct, complete answer.

Expected cost with randomness

When an algorithm makes random choices, its running time becomes a random variable, and we talk about expected (average) cost over the algorithm's own coin flips, not over the input. That is a stronger statement: for every input, the expected time is O(n log n). Let us see how stable the random-pivot quicksort really is by running it over many different random seeds on the same worst-looking input:

Python Spread of random pivot costs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every one of the fifty runs lands far below the theoretical worst case of n(n−1)/2; the spread between cheapest and costliest is small. That is the practical meaning of "expected O(n log n)": bad luck exists but is astronomically unlikely as n grows. We come back to this idea in randomized algorithms.

Computing an average with probabilities

For an average-case analysis, list the possible situations, give each a probability and cost, and add up probability × cost. Suppose a search succeeds with probability p (position uniform) and fails with probability 1 − p (cost n). The expected number of comparisons is

TEXT
E = p * (n + 1) / 2  +  (1 - p) * n
Python Expected comparisons by hit probability

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When every search succeeds, you pay about n/2. When every search fails, you pay n. Real workloads fall between those two numbers, but all of them are linear in n.

Which one should you report?

  • State the worst case by default; it is the safest promise.
  • Mention the average case when it differs a lot (quicksort, hash table lookups) and say what you assumed.
  • Mention the best case only if it teaches something (insertion sort on nearly sorted data).
  • If the cases are all the same (merge sort is Θ(n log n) always), say so: it is a virtue.

Common mistakes

  • Confusing the best case with Ω or the worst case with O. The cases are inputs; the bounds are about growth.
  • Assuming "average" means "typical for my data". The textbook average assumes a distribution (often uniform) that your data may not follow.
  • Quoting the best case as the complexity. "Insertion sort is O(n)" is false in general; it is O(n) only for sorted input.
  • Forgetting adversaries. If users control the input (web servers, hash tables), the worst case can actually be triggered.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. In linear search over n items, what is the worst-case number of comparisons?

    If the target is the last item or missing, every element is compared once, so n comparisons: O(n).
  2. 2. When is insertion sort's best case reached, and what is its cost?

    On sorted input each new item compares once with its left neighbor and stays put, so about n-1 comparisons in total.
  3. 3. Why does quicksort with the first element as pivot degrade to O(n²) on an already sorted list?

    With a sorted list the first item is the minimum, so each call peels off just one element. The sizes go n, n-1, n-2, ..., giving about n²/2 comparisons.
  4. 4. What does it mean for a randomized algorithm to have expected cost O(n log n)?

    The randomness is inside the algorithm, so the guarantee holds for each input individually, averaged over the random choices.
  5. 5. Which statement is correct?

    Cases select the input scenario. Bounds describe how the cost function grows. You can use any bound notation with any case.

Summary

  • The same algorithm can cost different amounts on different inputs of the same size, so we analyze best, worst and average cases.
  • Worst case is a guarantee and the default to report; average case needs an assumed input distribution; best case is rarely useful.
  • Linear search: best 1, worst n, average (n + 1) / 2 comparisons when the target is present.
  • Insertion sort is adaptive: O(n) on sorted input, O(n²) on reversed input.
  • Quicksort is O(n log n) on average but O(n²) with a bad pivot rule; random pivots make the expected cost O(n log n) for every input.
  • Cases are about inputs; O, Ω and Θ are about growth. Do not mix them up.

Next: Amortized Analysis