Beispiel zur Vorlesung 8: Bestimmen der Komplexitätsklasse bei einem Algorithmus, der eine "IF"-Anweisung enthält.


ergebnis := 0;

FOR i := 1 TO 100 DO
 IF n > 2 THEN
   FOR j := 0 TO n DO
     ergebnis := n * n;

Welche Komplexitätsklasse hat dieser Algorithmus, wenn man annimmt, dass eine Multiplikation in einem Schritt (= 1 Anweisung) ausgeführt wird?


Für alle n, die kleiner oder gleich 2 sind, wird KEINE Multiplikation ausgeführt, d.h.
O(1), wenn n <= 2.

Für alle anderen n (also für die, die größer als 2 sind), wird die Multiplikation 100 mal ausgeführt, d.h. O(n).