Visual walkthrough — Best, worst, average case — with examples

---

Step 1 — What we are counting

WHAT. We have an array — a row of boxes — holding $n$ items. We call it a, and its boxes are numbered $0,1,2,\dots ,n-1$. We are hunting for one value, the key, written $x$. The rule: read box $0$, then box $1$, and so on left-to-right, and stop the instant we find $x$.

WHY. Before we can average anything, we must agree on the single thing we tally. That thing is one comparison — the yes/no test "is the value in this box equal to $x$?". Every other cost (moving the finger, checking the loop) rides along with a comparison, so counting comparisons captures the running time.

PICTURE. The finger lands on box $0$ and asks its question. If "no", it slides right.

---

Step 2 — The two extremes we already understand

WHAT. Two arrangements are easy. If $x$ sits in box $0$, we stop after one comparison. If $x$ sits in the last box $n-1$ (or is not present at all), we make $n$ comparisons.

WHY. These are the [!definition] best and worst cases from the parent note. We show them first because the average must land somewhere between them — they are the guardrails that sanity-check our final answer.

PICTURE. Green finger stops at once (best). Red finger walks the whole row (worst).

$$B(n)=c(0)=0+1=1W(n)=c(n-1)=(n-1)+1=n$$

Here $B(n)$ reads "best cost for size $n$"; $W(n)$ reads "worst cost for size $n$". Notice both are just $c(i)$ evaluated at the luckiest ($i=0$) and unluckiest ($i=n-1$) box.

---

Step 3 — Why we cannot use one number

WHAT. For a fixed size $n$, the cost is not one value — it is a whole list of possible values: $1,2,3,\dots ,n$, one for each place the key could hide.

WHY. This is the heart of best/worst/average: the size is frozen, but the layout is free. A single number would be a lie. So we ask a fairer question — "if I do this search many, many times, what is the typical cost?"

PICTURE. A bar for each possible resting place, its height equal to the cost $c(i)=i+1$. The heights climb like a staircase.

---

Step 4 — Attaching a probability to each outcome

WHAT. To average, we must say how likely each resting place is. Our model (the "successful search, uniform" model from the parent) says: the key is present, and it is equally likely to be in any one of the $n$ boxes.

WHY. "Average" is meaningless until you name a distribution — this is exactly what Expected Value and Probability Distributions insists on. Equally likely is the honest default when we know nothing extra about the data.

PICTURE. Every box wears the same probability tag $\frac{1}{n}$.

$$\mathrm{Pr}(\text{key in box }i)=\underset{\begin{array}{c}\text{one box out}\\ \text{of }n\text{ equal ones}\end{array}}{\underbrace{\frac{1}{n}}}\text{for }i=0,1,\dots ,n-1$$

---

Step 5 — What "expected value" means, as a picture

WHAT. The expected value (or average case $A(n)$) is: multiply each possible cost by its probability, then add everything up.

$$A(n)=\sum _{i=0}^{n-1}\underset{\text{how likely}}{\underbrace{\mathrm{Pr}(\text{box }i)}}\times \underset{\text{what it costs}}{\underbrace{c(i)}}$$

WHY. Why this tool — a weighted sum — and not the plain midpoint $\frac{\text{best}+\text{worst}}{2}$? Because a plain midpoint ignores how often each outcome actually happens. The weighted sum is the mathematically honest "typical value". (For linear search the two happen to agree — but for Quicksort they wildly disagree, which is exactly why we build the honest tool.)

PICTURE. Each staircase bar from Step 3, now shrunk by its weight $\frac{1}{n}$; the average is where the whole shrunken pile balances.

---

Step 6 — Doing the sum with Gauss's trick

WHAT. Plug $\mathrm{Pr}=\frac{1}{n}$ and $c(i)=i+1$ into the expected-value sum and simplify.

$$A(n)=\sum _{i=0}^{n-1}\frac{1}{n}(i+1)=\frac{1}{n}\underset{\text{shift index}}{\underbrace{\sum _{i=0}^{n-1}(i+1)}}=\frac{1}{n}\underset{\begin{array}{c}k=i+1\\ \text{runs }1\text{ to }n\end{array}}{\underbrace{\sum _{k=1}^{n}k}}$$

WHY. The $\frac{1}{n}$ is the same for every term, so it slides out front — cleaning up the sum. Then relabel $k=i+1$: as $i$ runs $0\to n-1$, $k$ runs $1\to n$. Now we owe just "add up $1+2+\cdots +n$."

PICTURE — Gauss pairing. Pair the first with the last ($1+n$), the second with the second-last ($2+(n-1)$)… every pair equals $n+1$, and there are $\frac{n}{2}$ pairs.

$$\sum _{k=1}^{n}k=\underset{\text{each pair}}{\underbrace{(n+1)}}\times \underset{\text{number of pairs}}{\underbrace{\frac{n}{2}}}=\frac{n(n+1)}{2}$$

Feed it back:

$$A(n)=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{\cancel{n}(n+1)}{2\cancel{n}}=\boxed{\frac{n+1}{2}}\in \Theta (n)$$

The $n$'s cancel, leaving the clean $\frac{n+1}{2}$. In Asymptotic Notation (Big-O, Omega, Theta) this is $\Theta (n)$ — the same order as the worst case, because half of a big row is still a big row.

---

Step 7 — The degenerate cases (never leave a gap)

WHAT & WHY. A formula you trust must survive the weird inputs.

PICTURE. Three tiny arrays: empty, single box, and a failed search.

---

The one-picture summary

Everything at once: the staircase of costs, the uniform weights $\frac{1}{n}$, the Gauss pairing, and the balance point landing at $\frac{n+1}{2}$ between the best and worst guardrails.

Recall Feynman retelling — say it back in plain words

I'm looking for one card in a face-down row of $n$ cards, flipping left to right until I hit it. Counting: flipping until the card at position $i$ costs $i+1$ flips. Extremes: front card = $1$ flip (lucky), back card or missing = $n$ flips (unlucky). The catch: with $n$ fixed, the cost is a whole staircase $1,2,\dots ,n$, not one number — so I ask for the typical cost. Fairness rule: I assume the card is equally likely anywhere, so each spot gets weight $\frac{1}{n}$ (and those weights add to $1$, so it's legal). Averaging: typical cost = sum of (weight × cost) = $\frac{1}{n}(1+2+\cdots +n)$. Gauss magic: $1+2+\cdots +n$ pairs up into $\frac{n}{2}$ pairs each worth $n+1$, giving $\frac{n(n+1)}{2}$; the $\frac{1}{n}$ eats one $n$, leaving $\frac{n+1}{2}$ — I scan about half the row on average. Edges: one card → $1$; empty → formula sits out; card absent → always $n$. Same row length, but luck decides the flips.

Connections

• Parent: 3.1.03 Best, worst, average case — with examples (Hinglish) — same three cases, in Hinglish.
• Linear Search — the algorithm dissected here.
• Expected Value and Probability Distributions — the weighted-sum machinery of Step 5.
• Asymptotic Notation (Big-O, Omega, Theta) — why $\frac{n+1}{2}$ is $\Theta (n)$.
• Insertion Sort and Quicksort — where average and worst diverge far more dramatically.
• Amortized Analysis — averaging over a sequence, a different kind of average.