Berechnung der (worst- case- ) Zeitkomplexität
Elementare Operationen (Zuweisung, Ein-/ Ausgabe) : O ( l )
Summenregel:
T1 ( n ) und T2 ( n ) seien die Laufzeiten zweier Programmfragmente P1 und P2 ;
es gelte: T1 ( n ) ? O (f ( n ) ) und T2 ( n ) ? O ( g ( n ) ).
Für die Hintereinanderausführung von P1 und P2 ist dann
T(n) = T1 ( n ) + T2 ( n ) ? O ( max ( f ( n ), g ( n ) ) )
Produktregel:
z. B. für geschachtelte Schleifenausführung von P1 und P2
T(n) = T1 ( n ) * T2 ( n ) ? O ( f ( n ) * g ( n ) )