Cases
Best, worst, and average are three inputs, not three algorithms.
An algorithm is a precise, finite list of steps that turns an input into an output and is guaranteed to stop. Design invents the steps. Analysis asks two questions: does it do the right thing on every legal input, and how does the work grow?
We do not time it with a stopwatch. A stopwatch measures a laptop. A step count measures the algorithm.
| Case | Which input | What you use it for |
|---|---|---|
| Best | Fewest steps | A brag, not a guarantee |
| Worst | Most steps | The bound you can promise |
| Average | Typical, over many inputs | Useful, and usually harder to derive |
Same website, different crowd. A ticket onsale does not change its code at 10:00. Presale, first in line, is the friendliest input. General sale, deep in the queue, sold out when you arrive, is the meanest. You still publish the worst case, because that is the only experience you can promise.
Linear search
Walk \(A[0..N-1]\) from the left and stop at the first match.
- Best case: the target is in slot 0. One comparison. \(\Theta(1)\) for that input only.
- Worst case, found: the target is in the last slot. \(N\) comparisons.
- Worst case, missing: the target is not there. Also \(N\) comparisons, then failure.
Those two worst cases return different answers and cost the same. If the book is equally likely to sit anywhere, the average lands near \(N/2\) comparisons. That is still \(\Theta(N)\), with a smaller constant. \(N/2\) does not become \(\Theta(1)\).
Try this
A classmate says the average case is about \(N/2\), so the running time is \(\Theta(1)\) for practical purposes. What did they confuse?
Show the answer
They confused a smaller constant with a slower-growing class. \(N/2\) is still linear. \(\Theta(1)\) would mean the cost stops growing with \(N\).