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, thenThe 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$, soFor $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.