= Average-case analysis
<Average-case analysis> measures an <algorithm>'s expected cost when its inputs follow a specified <probability distribution>. If $T(x)$ is the number of counted operations on input $x$ and $p_n(x)$ is the probability of a size-$n$ input, then
$$
T_{\mathrm{avg}}(n)=\sum_{|x|=n}p_n(x)T(x).
$$
The <expected value> is meaningful only after specifying both the input model and the counted operation. It is not an average over arbitrary anecdotes or necessarily the cost of a typical individual run.
For a successful <linear search> through $n$ distinct entries, suppose the sought entry is equally likely to occupy any position. Searching from the beginning uses $i$ comparisons if the entry is at position $i$, so
$$
T_{\mathrm{avg}}(n)=\frac{1}{n}\sum_{i=1}^n i=\frac{n+1}{2}.
$$
For $n=9$, this is five comparisons, whereas <worst-case analysis> gives nine. If the entry is absent with probability $q$ and otherwise has the same equal-position model, the expected count becomes $qn+(1-q)(n+1)/2$. Changing the workload therefore changes the answer without changing the <algorithm>. <Amortized analysis> instead bounds the cost of a sequence of operations and need not assume an input <probability distribution>.
Back to article page
