# 2.4 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.

Chapter: Algorithm & Algorithm Analysis · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/best-average-worst

## Mental 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 $\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}$ 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.

## C++ code: counting comparisons per case

```cpp
#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";
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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²) |

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.

## Videos

- [Time Complexity #1](https://youtu.be/9TlHvipP5yA) (Abdul Bari): Works through how the same code takes different numbers of steps for different inputs.
- [Asymptotic Notations: Big Oh, Omega, Theta](https://youtu.be/A03oI0znAoc) (Abdul Bari): Links the three cases to the notations you meet next (O, Ω, Θ).

## Exam 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".

## Quick check

1. For linear search, the worst case happens when the key is…
   A. in the middle
   B. the first item
   C. the last item or not present
   D. repeated
   Answer: C. Then every item must be compared.

2. Best-case input for insertion sort is…
   A. a reversed array
   B. an already sorted array
   C. all equal except one
   D. random
   Answer: B. Each new key is already ≥ the item before it, so the inner while loop never runs. That gives O(n).

3. Why do we usually report the worst case?
   A. It is the easiest to compute
   B. It guarantees an upper limit for every input
   C. It is always the average
   D. It is the most common input
   Answer: B. Whatever the input, the algorithm will never be slower than this.

4. The best case of an algorithm depends on…
   A. n being 1
   B. the input arrangement for a given n
   C. the computer speed
   D. the language
   Answer: B. For a fixed size n, which arrangement of the data makes it fastest?

## Practice

**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?

Solution:

- 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.

**Problems:**

- [Search Insert Position](https://leetcode.com/problems/search-insert-position/) (easy). Hint: Write the linear version first and name its best and worst case. Then do it in O(log n) with binary search.
- [Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/) (easy). Hint: Counting digits by dividing by 10 depends on the value. What is the worst case per number?

## Mastery checklist

- [ ] I can define best, average and worst case.
- [ ] I can give the input that triggers each case for linear search and insertion sort.
- [ ] I can derive (n + 1)/2 for the average successful linear search.
- [ ] I can explain why we usually analyse the worst case.