bei der Untersuchung der Komplexität von Algorithmen und von Problemen die Betrachtung des durchschnittlichen Verhaltens, entweder bezogen auf Wahrscheinlichkeitsverteilungen über den Mengen von Eingaben gleicher Länge, oder in randomisierten Algorithmen (randomisierter Algorithmus), bezogen auf die verwendeten Zufallsbits.

Das wichtigste Maß für die Komplexität im Mittel ist die average case-Rechenzeit.