Exercises — Best, worst, average case — with examples

$T(I)$ = number of operations on input $I$.

• $\min$ = "the smallest such value over all inputs of that size" = least work = best case, $B(n)={\min }_{|I|=n}T(I)$.
• $\max$ = "the largest such value over all inputs of that size" = most work = worst case, $W(n)={\max }_{|I|=n}T(I)$.

False. The worst case is measured at a fixed size $n$; you vary the arrangement, not the size. Insertion sort's worst case is a reverse-sorted array of that size $n$. Size and case are independent axes.

• (a) match at the very first slot → stops after 1 comparison → best case.
• (b) absent → must scan all $n$ slots → worst case.
• (c) uniform over positions → take the expected cost → average case.

• Best: match at index 0 → $B=1$.
• Worst: match at index 9 (last slot) → $W=10$.
• Average: cost at index $i$ is $i+1$, each with probability $\frac{1}{10}$. Using the Gauss sum ${\sum }_{k=1}^{10}k=\frac{10\cdot 11}{2}=55$: $A=\frac{1}{10}{\sum }_{i=0}^9(i+1)=\frac{1}{10}{\sum }_{k=1}^{10}k=\frac{55}{10}=\mathrm{5.5.}$ So $B=1,W=10,A=5.5$.

Reverse-sorted is the worst case: each new key sinks all the way to the front. Outer iteration $i$ (for $i=1\dots n-1$) does $i$ comparisons: $W={\sum }_{i=1}^{5}i=\frac{5\cdot 6}{2}=15.$

Sorted is the best case: the while test a[j] > key fails immediately every time, so each of the $n-1$ outer iterations does exactly 1 comparison: $B=n-1=6-1=5.$

The inner while loop's length is decided by how far the new key must sink to reach its sorted position.

• Sorted input (blue path, figure): each new element is already $\ge$ everything before it, so the loop condition is false on its first test. That's 1 comparison per outer step → $n-1$ total → linear, $\Theta (n)$.
• Reverse input (pink path): each new element is smaller than everything before it, so the loop walks the entire prefix — $i$ comparisons on step $i$. Summing $1+2+\cdots +(n-1)=\frac{(n-1)n}{2}$ → quadratic, $\Theta (n^2)$.

The difference is how much of the prefix the inner loop traverses: a constant amount vs a growing amount. That growing-vs-constant is exactly the $n^2$-vs-$n$ gap — and it is the widening yellow band in the figure.

Best $=1$, worst $=n$, so their midpoint is $\frac{1+n}{2}=\frac{n+1}{2}$ — which matches the average. Why it coincides here: the cost $T(i)=i+1$ is a straight line in the index $i$, and the index is uniformly distributed. The mean of a linear function under a uniform, symmetric distribution lands exactly at the midpoint. Why it fails in general: the average is ${\sum }_I\mathrm{Pr}(I)T(I)$, weighting each cost by how often it occurs. When extreme inputs are rare, they barely move the average. Quicksort is the poster child: best $\Theta (n\log n)$, worst $\Theta (n^2)$, but the $\Theta (n^2)$ layouts are so rare that the average stays $\Theta (n\log n)$ — nowhere near the midpoint.

Split by the two disjoint events, then use $A=\sum \mathrm{Pr}\cdot \text{cost}$:

• Absent (prob $p$): scan all $n$ slots → cost $n$.
• Present (prob $1-p$): expected cost is the earlier $\frac{n+1}{2}$.

$A(n)=p\cdot n+(1-p)\cdot \frac{n+1}{2}.$ Sanity checks: $p=1$ gives $n$ (always absent → always full scan); $p=0$ gives $\frac{n+1}{2}$ (matches the successful-search result). Both extremes behave correctly.

Modeling assumption (declared): the input is a uniformly random permutation of $n$ distinct values — every ordering equally likely. Under this model, when we insert element $i$ into the already-sorted prefix of length $i$, its correct rank is uniform over the $i+1$ possible slots, so it displaces, on average, about half of the prefix. That justifies "sinks halfway," costing $\approx i/2$ comparisons.

Sum over the outer loop $i=1\dots n-1$: $A(n)\approx {\sum }_{i=1}^{n-1}\frac{i}{2}=\frac{1}{2}{\sum }_{i=1}^{n-1}i=\frac{1}{2}\cdot \frac{(n-1)n}{2}=\frac{n(n-1)}{4}.$ The leading term is $\frac{n^2}{4}$, so $A(n)\in \Theta (n^2)$ — same order as the worst case, but with a constant factor of roughly half. That halved constant is exactly why insertion sort beats its worst case by a factor of 2 on typical data, yet still cannot escape $\Theta (n^2)$. See Insertion Sort.

Fix one cost model at a time.

Model A — count only key-equality comparisons a[i] == x. Because the key is genuinely present at some uniform real index $i\in \{0,\dots ,n-1\}$, the loop stops at that real slot after $i+1$ equality comparisons; the sentinel copy is never reached. So this count is identical to plain linear search: $A(n)=\frac{1}{n}{\sum }_{i=0}^{n-1}(i+1)=\frac{n+1}{2}.$ For $n=10$ this is $5.5$, matching L2.1. The sentinel changes this count by zero.

Model B — count the loop-control bound checks i < n (a different operation). Plain search evaluates this bound test once per iteration. The sentinel version removes it entirely: the loop is guaranteed to terminate on a match, so no i < n guard is needed each pass. This is the only thing the sentinel saves — one bound test per iteration, i.e. a per-iteration constant.

Bottom line: the sentinel leaves the equality-comparison count ($\frac{n+1}{2}$, class $\Theta (n)$) untouched and trims a different operation (the bound check). Same $\Theta (n)$ class either way.

(If the key could be absent, the scan would reach the sentinel copy at index $n$ and stop there, costing $n+1$ equality comparisons for that absent event — weighted by the absence probability, as in L3.3.)

Best $=1$, worst $=100$, midpoint $=\frac{1+100}{2}=50.5$. Average: $A=0.9\cdot 1+0.1\cdot 100=0.9+10=\mathrm{10.9.}$ The average $10.9$ is far below the midpoint $50.5$, because the expensive input is rare (only $10\%$). In the figure, the tall pink bar (cost $100$) is thin (weight $0.1$); its contribution to the mean is just its height times its width, so the yellow "mean" line sits low, near the fat cheap bar. This concretely disproves "average = (best+worst)/2".

Quicksort's cost is driven by how balanced each partition is. A balanced split (pivot near the median) gives recursion depth ${\log }_{2}n$ with $\Theta (n)$ work per level → $\Theta (n\log n)$. The worst case needs consistently terrible pivots (e.g. always the min/max), which for random data is astronomically unlikely. Averaging over all input orders, most partitions are "good enough", so the expected depth stays $O(\log n)$ → average $\Theta (n\log n)$. Randomizing the pivot (Quicksort) makes the algorithm — not the input — supply the randomness, so no fixed adversarial input can force the $\Theta (n^2)$ case reliably. The average is therefore governed by the common balanced splits, landing near the best, not the midpoint.

• Average-case averages over the space of inputs under a probability distribution: "for a random array, how long does linear search take?" It answers questions about typical inputs.
• Amortized averages the cost of a sequence of operations on one data structure, with no probability — it's a worst-case guarantee spread over the sequence. Example: a dynamic array's push is $\Theta (1)$ amortized because the rare $\Theta (n)$ resize is paid for by many cheap pushes.

Right tool: use average-case when inputs are drawn randomly and you want the expected time; use amortized when a single expensive step is provably rare within a guaranteed sequence, regardless of input randomness.

Refuted by an explicit algorithm. Consider count_zeros(a[0..n-1]):

c = 0
for i in 0..n-1:          # always n loop iterations
    if a[i] == 0:         # 1 comparison each iteration
        c = c + 1         # extra op only when a[i] == 0
return c

Count the basic operations (comparison, plus the increment when a zero is found):

• The loop always does exactly $n$ comparisons, regardless of contents.
• It does an extra increment for each zero. Let $z$ = number of zeros in the input, $0\le z\le n$.

So $T(I)=n+z$. Now check the three cases at fixed size $n$:

• Best: no zeros ($z=0$) → $T=n$, so $B(n)=n\in \Theta (n)$.
• Worst: all zeros ($z=n$) → $T=2n$, so $W(n)=2n\in \Theta (n)$.
• Average: if each slot is zero with probability $\frac{1}{2}$, expected zeros $=n/2$ → $A(n)=n+\frac{n}{2}=\frac{3n}{2}\in \Theta (n)$.

All three cases are $\Theta (n)$, yet $T(I)$ ranges over $\{n,n+1,\dots ,2n\}$ across inputs — it is not the single value $n$. This refutes the claim: $\Theta (n)$ pins the order of growth, never the exact per-input count.

Best is min, Worst is max, Average is the probability-weighted mean — all at the same $n$, and all reported in the bound language of Asymptotic Notation (Big-O, Omega, Theta).