The sum of costs of an algorithm over all possible inputs divided by the number of possible inputs.