die durchschnittliche Rechenzeit eines Algorithmus auf Eingaben der gleichen Länge.

Zu unterscheiden ist, ob bei deterministischen Algorithmen eine Wahrscheinlichkeitsverteilung auf der Menge der Eingaben gegebener Länge vorgegeben ist und der Durchschnitt bezüglich dieser Verteilung gebildet wird, oder ob bei randomisierten Algorithmen für jede Eingabe die durchschnittliche Rechenzeit bezüglich der Zufallsentscheidungen des Algorithmus gebildet wird. Im zweiten Fall ist der worst case (worst case-Rechenzeit) der durchschnittlichen Rechenzeiten für Eingaben der gleichen Länge von Interesse.

Für viele praktische Probleme wie das Rucksackproblem oder das Traveling-Salesman-Problem läßt sich eine angemessene Wahrscheinlichkeitsverteilung auf der Menge der Eingaben gegebener Länge nicht angeben.