averagecase

In computer science, the average-case complexity or average-case performance of an algorithm is the expected resources (time or space) required to solve a problem, averaged over a specified probability distribution of inputs. It contrasts with worst-case (maximum resource use over all inputs) and best-case (minimum resources). The choice of input distribution is essential and can greatly influence the result.

To compute, we define a random input I following distribution D, and a cost function T(I). The average-case time is E_D[T(I)]. In discrete inputs, it is the sum over all I of T(I) P(I). In practice, D is chosen to reflect realistic usage, or simpler models like uniform randomness or random permutations.

Well-known examples: Quicksort on uniformly random input has average-case time O(n log n), while its worst-case is O(n^2). Hash table operations often have favorable average-case times under assumed hash distributions, though worst-case can be poor if many collisions occur. Binary search typically has logarithmic time on most distributions, and matches its worst-case bound on the same input class.

Limitations: Average-case analysis depends on assumptions about input distribution, which may be unknown or adversarial. Real-world performance may diverge from theoretical averages due to data locality, caching, parallelism, or implementation details. As a result, other analyses such as amortized analysis (average over a sequence of operations) or smoothed analysis (average under slight random perturbations of worst cases) are used to capture practical behavior.

The term is widely used in algorithm design, data structures, and analysis of probabilistic algorithms.