the lower bound for finding the maximum
To find the largest of n numbers, the natural method is a single sweep: hold a running champion, compare it to each next element, and keep the bigger one. That uses n-1 comparisons. Could a smarter scheme use fewer? The lower bound says no: every comparison-based algorithm needs at least n-1 comparisons in the worst case to find the maximum. The simple sweep is exactly optimal — there is no cleverness to be had.
The cleanest proof is a 'tournament' or accounting argument. Think of the maximum as the unique winner of a knockout tournament: an element can be ruled out as the maximum only by losing at least one comparison. There are n elements, and all but one (the true maximum) must be eliminated, so at least n-1 elements must each suffer a loss. But a single comparison produces exactly one loser. Therefore you need at least n-1 comparisons to generate n-1 losses. An adversary makes this airtight: it answers each comparison so that the reported loser is some element that has never lost before (always possible while two unbeaten elements remain), guaranteeing each comparison eliminates at most one fresh candidate, so fewer than n-1 comparisons leave two elements that could each still be the max.
This is a satisfying case where the obvious algorithm and the lower bound shake hands at exactly n-1, so the problem's comparison complexity is precisely n-1 — not just Theta(n) but the exact count. The honest scope notes: it is a comparison-model, worst-case bound; it counts comparisons, not data movement; and it concerns finding only the maximum. Asking for more — the max AND the min, or the second largest, or the median — changes the count, and each has its own tighter analysis. In particular, finding max and min together does NOT cost 2(n-1); a smarter pairing does better, which the next entry explains.
With 5 elements, the sweep does 4 comparisons (champion vs. each of the other 4) and the lower bound is also 5-1 = 4. To declare a winner you must give the other 4 at least one loss each, and each comparison yields one loss, so 4 is unavoidable and sufficient.
Each comparison makes one loser; n-1 losers must be produced, so >= n-1 comparisons.
n-1 is the exact comparison count, not merely Theta(n) — there is no constant-factor slack here. But it is comparisons only and worst-case only; it says nothing about finding the max and min together, which is cheaper per element than doing each separately.