Worst-case analysis ($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 isThe 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.^[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.