= Worst-case analysis
{title2=$T_{\max}(n)$}
<Worst-case analysis> measures the largest resource use of a specified <algorithm> among inputs of the same size. If $T(x)$ counts operations on input $x$, the worst-case function is
$$
T_{\max}(n)=\max_{|x|=n}T(x).
$$
The cost model and meaning of input size $n$ are part of the definition. A <big O notation> bound describes growth of this function, rather than a claim about how often the difficult input occurs.<Algorithms by Jeff Erickson>[Introduction, algorithm analysis and worst-case running-time convention]{ref}
For <linear search> of $n$ entries, looking for an absent item requires $n$ equality tests; finding the first item needs just one. Thus the worst-case comparison count is $n$, even if many actual queries finish earlier. This supplies a guarantee for every allowed input, while an <average-case analysis> requires a stated distribution over inputs.
Back to article page
