Analyse des erwarteten Verhaltens von Algorithmen, insbesondere der average case-Rechenzeit.

Bei deterministischen Algorithmen und zufälligen Eingaben und bei randomisierten Algorithmen ist die Rechenzeit eine Zufallsvariable, mit deren Analyse sich die average case-Analyse befaßt.

Neben dem Erwartungswert sind die Varianz und höhere Momente ebenso von Interesse wie obere Schranken, die mit sehr nahe bei 1 liegender Wahrscheinlichkeit unterschritten werden.