Foundation · Module 1 · Lesson 2
Best, average, and worst case
How the same algorithm behaves across different inputs.
Lesson 2 of 123
1d streakDetailed theory
A single algorithm can perform different amounts of work on different inputs of the same size. Case analysis describes that variation; asymptotic notation describes the growth within a chosen case.
By the end, you can
- Construct best-case and worst-case inputs.
- Understand why average case needs an input distribution.
- Avoid confusing input cases with O, Ω, and Θ.
Vocabulary
Definitions with concrete meaning
Best case
The minimum cost among all valid inputs of size n.
Worst case
The maximum cost among all valid inputs of size n.
Average case
The expected cost across inputs under a stated probability distribution—not merely (best + worst) / 2.
Expected complexity
An expectation over randomness in the algorithm, the input, or both; the source of randomness must be stated.
Rules to apply
- 1Hold input size n fixed while comparing different arrangements or values.
- 2Define exactly what counts as success, failure, and a primitive operation.
- 3Worst-case bounds give guarantees; average-case bounds need probability assumptions.
- 4A case can have a tight Θ bound: best-case Θ(1), worst-case Θ(n).
- 5Do not use Ω as a synonym for best case or O as a synonym for worst case.
Worked example 1
Linear search across all three cases
Search an unsorted array of n values from left to right.
for i = 0 to n - 1:
if a[i] == target: return i
return -1- 1
Best input
Target is at index 0, so one comparison is made: Θ(1).
- 2
Worst input
Target is absent or last, so n comparisons are made: Θ(n).
- 3
Average assumption
Assume the target exists and each index is equally likely. Expected comparisons are (1 + 2 + … + n) / n = (n + 1) / 2.
The average is Θ(n), even though the best case is constant.
Worked example 2
Why quicksort has different cases
Partition around a pivot, then recursively sort both sides.
- 1
Balanced partitions
Two subproblems of about n/2 create log n levels with Θ(n) work per level.
- 2
Highly unbalanced partitions
Subproblem sizes n−1 and 0 create n levels, each doing a shrinking linear partition.
- 3
State the result
Balanced: Θ(n log n). Repeated worst pivots: Θ(n²).
Random pivot selection protects the expected runtime, but it does not remove the quadratic worst case.
Comparison table
Case comparison
Always read each cell as a bound for the named case and assumptions.
| Algorithm / operation | Best | Average / expected | Worst |
|---|---|---|---|
| Linear search | Θ(1) | Θ(n) | Θ(n) |
| Binary search | Θ(1) | Θ(log n) | Θ(log n) |
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) |
| Randomized quicksort | Θ(n log n) | Expected Θ(n log n) | Θ(n²) |
| Hash-table lookup | Θ(1) | Expected Θ(1) | Θ(n) |
Check your understanding
1Is the average case always halfway between best and worst?
No. It is a weighted expectation over inputs and requires a probability distribution.
2Does Ω(n) mean “best-case linear”?
No. Ω is a lower-bound notation and can describe any selected case. Always name the case separately.
3Why do engineers often emphasize worst case?
It supplies a guarantee, which matters for latency limits, real-time systems, and adversarial inputs.
Cost Model
Complexity & Trade-offs
When to use it
- Choosing between expected speed and hard latency guarantees.
- Understanding behavior on sorted, random, duplicated, or adversarial inputs.
- Explaining randomized algorithms and hash-table performance accurately.
Common mistakes
- Calculating average case as (best + worst) / 2.
- Using O, Ω, and Θ as replacements for worst, best, and average case.
- Claiming expected performance without identifying the source of randomness.
Practice prompts
- Analyze linear search when the target is absent with probability 1/2.
- Construct best and worst inputs for insertion sort.
- Explain expected versus worst-case lookup in a hash table.
Mastery check