Sei T(n) Anzahl der Schritte des Algorithmus bei Eingabe einer Folge der Länge n.
Es gilt: T(n) = 2 T(n/2) + C . n Da T(1) konstant (T(1) = C1) erhält man T(n) = Q(n log n).
Beispiele: T(1) = C1 T(2) = 2C1+ 2C T(4) = 4C1 + 8C T(8) = 8C1 + 24 C T(16) = 16C1 + 64 C T(32) = 32C1 + 160 C Gleichungen wie die obige nennt man Rekursionsgleichungen.
(Sie treten bei Komplexitätsanalysen oft auf.)