Best, Average & Worst Case
The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Looking for your keys in a row of 10 pockets: if they’re in the first pocket you’re done in one check; if they’re in the last pocket (or not there at all) you check all 10. Same algorithm, same n, very different effort.
The three cases
- Best case: the input arrangement that needs the fewest steps. Linear search: key at index 0 → 1 comparison.
- Worst case: the arrangement that needs the most steps. Linear search: key last or missing → n comparisons.
- Average case: the expected steps over all inputs (assuming each is equally likely). Linear search, key present: on average comparisons.
Which one do we report?
Usually the worst case, because:
- it is a guarantee: the algorithm will never be slower;
- it often happens in practice (searching for something that isn’t there);
- the average case needs assumptions about the input that may not hold.
The case is about the input arrangement for a fixed n. “n = 1” is not the best case. A sorted array of size 1,000,000 can be the best case for insertion sort.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
int comparisons;
int linearSearch(const int a[], int n, int key) {
for (int i = 0; i < n; i++) {
comparisons++;
if (a[i] == key) return i;
}
return -1;
}
int main() {
int a[] = {8, 3, 14, 6, 21, 9, 17, 2};
int n = 8;
struct { const char* label; int key; } cases[] = {
{"best (first item)", 8}, {"middle", 6}, {"worst (missing)", 99}};
for (auto c : cases) {
comparisons = 0;
int pos = linearSearch(a, n, c.key);
cout << c.label << ": key " << c.key << " -> index " << pos
<< " after " << comparisons << " comparisons\n";
}
// Average over every key that is present: (1 + 2 + ... + n) / n = (n + 1) / 2
int total = 0;
for (int i = 0; i < n; i++) { comparisons = 0; linearSearch(a, n, a[i]); total += comparisons; }
cout << "average when found: " << total << "/" << n << " = " << (double)total / n << "\n";
}best (first item): key 8 -> index 0 after 1 comparisons middle: key 6 -> index 3 after 4 comparisons worst (missing): key 99 -> index -1 after 8 comparisons average when found: 36/8 = 4.5
05Complexity
| Linear search: best (key is first) | O(1): 1 comparison |
|---|---|
| Linear search: average (key present) | (n + 1) / 2 comparisons → O(n) |
| Linear search: worst (last or missing) | n comparisons → O(n) |
| Bubble sort with flag: best / worst | O(n) / O(n²) |
| Extra space | O(1) |
The worst case is an upper bound you can promise to a user, which is why it is the one usually reported.
06Watch
Time Complexity #1
Why this one: Works through how the same code takes different numbers of steps for different inputs.
Asymptotic Notations: Big Oh, Omega, Theta
Why this one: Links the three cases to the notations you meet next (O, Ω, Θ).
07Exam lens
Likely questions
- Define best, worst and average case complexity with linear search as the example.
- Why is worst-case analysis used more often than average-case analysis?
- Give an input that produces the best case and the worst case for insertion sort.
- Show that the average number of comparisons for a successful linear search is (n + 1)/2.
Common mistakes
- "Best case is when n is small." No: best case is about the arrangement of the input for a given n, never about a small n.
- Thinking the average case is (best + worst) / 2. It is an expected value over all inputs.
- Mixing up the case with the notation. "Worst case" is not the same thing as "Big-O".
08Quick check
09Practice
🟢 Trace by hand
Count comparisons for linear search in [4, 9, 2, 7, 5] with keys 4, 2, 5 and 8. Which is the best case and which is the worst?
Show answer
- key 4: 1 comparison (best)
- key 2: 3 comparisons
- key 5: 5 comparisons
- key 8: 5 comparisons, not found (worst, tied with 5)
🟡 Implement it
Add a comparison counter to insertion sort and print it for a sorted, a reversed and a random array of 10 items.
Hint
Sorted → 9 comparisons (n − 1). Reversed → 45 (n(n−1)/2). Random falls somewhere in between.
🔴 Solve problems
Hint
Write the linear version first and name its best and worst case. Then do it in O(log n) with binary search.
Hint
Counting digits by dividing by 10 depends on the value. What is the worst case per number?
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.