Worked examples — Best, worst, average case — with examples

Before any example: a single reminder of the three quantities, in plain words.

---

The scenario matrix

Every case-analysis problem is really one of these cells. The worked examples below are tagged with the cell they cover, so together they fill the whole grid.

Cell	What it stresses	Covered by
C1 Best (early exit)	luckiest arrangement, loop stops at once	Ex 1
C2 Worst (full scan)	unluckiest arrangement, target absent	Ex 1, Ex 4
C3 Average (uniform position)	probability-weighted mean, Gauss sum	Ex 2
C4 Degenerate: empty input $n=0$	limiting/edge value, loop never runs	Ex 3
C5 Degenerate: single element $n=1$	smallest non-trivial size	Ex 3
C6 Ties / duplicates	equal keys change which branch runs	Ex 5
C7 Rare-bad case (avg $\ne$ midpoint)	why average hugs best when bad is rare	Ex 6
C8 Limiting behaviour $n\to \infty$	which case dominates asymptotically	Ex 7
C9 Real-world word problem	translating a story into $B/W/A$	Ex 8
C10 Exam twist (partial info / unsuccessful-search probability)	mixed distribution, don't assume 100% hits	Ex 9

Everything below points back to Linear Search, Insertion Sort and Quicksort, and leans on Expected Value and Probability Distributions and Asymptotic Notation (Big-O, Omega, Theta).

---

Ex 1 — Best & Worst of Linear Search (cells C1, C2)

Forecast: guess before reading. How many comparisons for a value sitting in slot 0? For a value that isn't there at all?

The picture first — the array as a row of boxes and where the search stops.

1. (a) Locate $x=7$. Why this step? Best case means the cheapest arrangement — an early exit. Here a[0]==7 is true on the first comparison, so the loop returns immediately. $B=1$
2. (b) Search $x=8$. Why this step? Worst case forces the loop to test every slot. $8$ never matches, so we compare against all $5$ elements, fail every time, then return $-1$. $W=5=n$

Verify: count the green ticks in the figure — one for (a). Count the red crosses for (b) — five, one per box, matching $n=5$. ✓ Best $=\Theta (1)$, Worst $=\Theta (n)$ as the pocket table promised.

---

Ex 2 — Average of Linear Search, the honest way (cell C3)

Forecast: roughly half of 5? A little more? A little less? Write your guess.

1. Cost when $x$ is at index $i$. Why this step? We must know $T(I)$ for each arrangement before we can average. If the match is at index $i$ (starting from $0$), we compared against slots $0,1,\dots ,i$ — that's $i+1$ comparisons.
2. Attach probabilities. Why this step? "Equally likely" means $\mathrm{Pr}=\frac{1}{n}$ for each position — this is the uniform distribution. Average is $\sum \mathrm{Pr}(I)T(I)$, not the midpoint of extremes. $A={\sum }_{i=0}^{n-1}\frac{1}{n}(i+1)=\frac{1}{n}{\sum }_{k=1}^{n}k$
3. Apply the Gauss sum. Why this step? ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}$ collapses the sum into a formula (pair the smallest with the largest: $1+n,2+(n-1),\dots$). $A=\frac{1}{n}\cdot \frac{n(n+1)}{2}=\frac{n+1}{2}=\frac{5+1}{2}=3$

Verify: list all five costs $1,2,3,4,5$; their plain mean is $\frac{1+2+3+4+5}{5}=\frac{15}{5}=3$. ✓ Matches $\frac{n+1}{2}$. On average we scan a bit past halfway.

---

Ex 3 — Degenerate sizes: empty and single (cells C4, C5)

Forecast: can an algorithm do zero work? Can best equal worst?

1. (a) $n=0$. Why this step? Edge inputs are where formulas either shine or break — you must check them. The loop body for i in 0..n-1 runs zero times because there is no valid $i$. Zero comparisons, straight to return -1. $B(0)=W(0)=A(0)=0$
2. Sanity-check the formula at the edge. Why this step? Our worst-case formula was $W(n)=n$; plugging $n=0$ gives $0$. The successful-average $\frac{n+1}{2}$ is undefined here — there is no element to succeed on, so "successful average" simply doesn't apply. Good: the edge exposes an assumption.
3. (b) $n=1$. Why this step? The smallest non-trivial case: there is only one arrangement, so best, worst and average must all coincide. One comparison against a[0]. $B(1)=W(1)=A(1)=1$

Verify: formula $\frac{n+1}{2}$ at $n=1$ gives $\frac{2}{2}=1$, and $W(n)=n$ gives $1$. Both agree with the direct count. ✓ Whenever there is a single possible input, the three cases are forced equal.

---

Ex 4 — Insertion Sort worst case, reverse-sorted (cell C2)

Forecast: each new element must travel to the very front — will the total look like $n$ or like $n^2$?

The step figure shows each key sinking all the way left.

1. Count per outer iteration. Why this step? Worst case for insertion sort is reverse order, because every new key is smaller than all before it, so the inner while runs until it falls off the front. Iteration $i$ (with $i=1,2,3$) does exactly $i$ comparisons.

• $i=1$: insert $3$ → $1$ comparison.
• $i=2$: insert $2$ → $2$ comparisons.
• $i=3$: insert $1$ → $3$ comparisons.

2. Sum them. Why this step? Total comparisons is the sum over outer iterations, a triangular number. $W(4)={\sum }_{i=1}^{n-1}i=\frac{(n-1)n}{2}=\frac{3\cdot 4}{2}=6$

Verify: $1+2+3=6$. ✓ Formula $\frac{(n-1)n}{2}$ grows like $\Theta (n^2)$ — the whole point that insertion-sort worst case is an order above its best case $\Theta (n)$.

---

Ex 5 — Ties change the branch (cell C6)

Forecast: duplicates — do they cost a lot (like reverse-sorted) or almost nothing?

1. Evaluate the strict test on equal keys. Why this step? The exact comparison operator decides the branch. With key = 5 and a[j] = 5, the test 5 > 5 is false. So the inner loop stops immediately — no shifting.
2. One comparison per outer iteration. Why this step? Each of the $n-1$ outer passes does a single failing comparison, exactly like an already-sorted array. $T=n-1=3-1=2$

Verify: direct trace — $i=1$: 5>5 false (1 comp); $i=2$: 5>5 false (1 comp). Total $2=n-1$. ✓ Equal keys hit the best case here only because the operator is strict >. Had it been >=, ties would shift and this would explode to worst case — the operator, not the values, decides.

---

Ex 6 — Average $\ne$ (best+worst)/2 for Quicksort (cell C7)

Forecast: is the true average nearer the cheap end or the expensive end?

1. Compute each extreme's magnitude. Why this step? We need concrete numbers to see how far the midpoint sits from reality. With $n=1024=2^{10}$, so ${\log }_{2}n=10$: $\text{best}\approx n{\log }_{2}n=1024\cdot 10=10,240,\text{worst}\approx n^2=1,048,576.$
2. Form the naive midpoint. Why this step? This is the myth we're debunking. $\frac{\text{best}+\text{worst}}{2}=\frac{10,240+1,048,576}{2}=529,408.$
3. State the true average. Why this step? The average is $\sum \mathrm{Pr}(I)T(I)$; bad pivots are rare, so their huge cost is multiplied by a tiny probability and barely moves the mean. Quicksort's average is $\Theta (n\log n)\approx 10,240$ — essentially the best order, not the midpoint.

Verify: ratio of midpoint to true average $=\frac{529,408}{10,240}\approx 51.7$. ✓ The naive midpoint overestimates by ~50×. Average is a weighted mean; rarity of the bad case drags it down toward best.

---

Ex 7 — Limiting behaviour, which case wins (cell C8)

Forecast: does the worst/best ratio settle to a constant, or keep growing?

1. Form the ratio. Why this step? Comparing growth rates is exactly what asymptotics is for — it strips constants and reveals the order gap. $\frac{W(n)}{B(n)}=\frac{\frac{(n-1)n}{2}}{n-1}=\frac{n}{2}.$
2. Take the limit. Why this step? The limiting cell asks what happens for huge inputs. ${\lim }_{n\to \infty }\frac{W(n)}{B(n)}={\lim }_{n\to \infty }\frac{n}{2}=\infty .$

Verify: at $n=4$ the ratio is $\frac{6}{3}=2=\frac{4}{2}$. ✓ Because the ratio $\to \infty$, best and worst are not the same order — an entire factor of $n$ apart. This is why saying "insertion sort is $\Theta (n^2)$" without a case qualifier hides the fast nearly-sorted behaviour.

---

Ex 8 — Real-world word problem (cell C9)

Forecast: worst near 0.4 s? Average about half that?

1. Model as linear search. Why this step? One unsorted pass, stop on first match — this is Linear Search. Comparisons ↔ box reads.
2. (a) Worst-case reads. Why this step? Unluckiest layout: requested box is last, forcing $W=n=200$ reads. $t_{\text{worst}}=200\times 2\text{ ms}=400\text{ ms}.$
3. (b) Average reads. Why this step? Uniform position → average reads $\frac{n+1}{2}=\frac{201}{2}=100.5$. $t_{\text{avg}}=100.5\times 2\text{ ms}=201\text{ ms}.$

Verify (units): reads $\times$ (ms/read) $=$ ms. ✓ $400\text{ ms}=0.4\text{ s}$ worst, $201\text{ ms}\approx 0.2\text{ s}$ average — average is close to half the worst, exactly the linear-search story in physical time.

---

Ex 9 — Exam twist: search that might fail (cell C10)

Forecast: should the answer sit between $\frac{n+1}{2}=5.5$ and $n=10$? Where exactly?

1. List the two outcomes and their costs. Why this step? This is a mixed distribution — the exam trap is assuming every search succeeds. Success cost $=\frac{n+1}{2}=5.5$; failure cost $=n=10$.
2. Weight by probability (law of total expectation). Why this step? Overall expected cost $=\sum \mathrm{Pr}(\text{outcome})\times \text{cost}$, blending the two sub-cases from Expected Value and Probability Distributions. $A=p\cdot \frac{n+1}{2}+(1-p)\cdot n=0.7(5.5)+0.3(10).$
3. Compute. $A=3.85+3.0=6.85\text{ comparisons}.$

Verify: $6.85$ lies between $5.5$ (all-success) and $10$ (all-fail), leaning toward success since $p=0.7$. ✓ Check endpoints: at $p=1$, $A=5.5$; at $p=0$, $A=10$ — both recovered by the formula.

---

Recall Which cell did each example fill?

Ex1 ::: C1 best + C2 worst (linear search) Ex2 ::: C3 average, uniform position Ex3 ::: C4 empty input + C5 single element Ex4 ::: C2 worst insertion sort (reverse) Ex5 ::: C6 ties, strict operator matters Ex6 ::: C7 rare-bad, average $\ne$ midpoint Ex7 ::: C8 limiting ratio $W/B\to \infty$ Ex8 ::: C9 real-world conveyor word problem Ex9 ::: C10 exam twist, mixed success/fail distribution

Connections

• Parent: Best/Worst/Average — the recipe these examples exhaust.
• Linear Search — Ex 1, 2, 3, 8, 9.
• Insertion Sort — Ex 4, 5, 7.
• Quicksort — Ex 6, the rare-bad-pivot lesson.
• Expected Value and Probability Distributions — averaging in Ex 2, 6, 9.
• Asymptotic Notation (Big-O, Omega, Theta) — the order language in Ex 6, 7.
• Amortized Analysis — a different averaging (over a sequence, not over inputs).