a)
Schleife 1 : n/8 Ausführungen
Schleife 2 : n/4 Ausführungen
Schleife 3 : unabhängig von n
Weil die Schleifen verschachtelt sind, gehen die Ausführungen multiplikativ ein (ist bei allen Aufgaben so).
LZ(n) = n/8 * n/4 = n^2/32 € O(n^2)
Stünden die Schleifen hintereinander, dann sähe es so aus
LZ(n) = n/8 + n/4 = 3n/8 € O(n)
b)
Schleife 1 : 2n Ausführungen
Schleife 2 : log_2(n) Ausführungen
LZ(n) = 2n * log_2(n) € O(n * log(n))
c)
Angenommen der Code lautet (Schreibfehler ?)
for(j=0, j < n; j++)
for (k = 0, k < j; k++)
sum = sum+1
dann werden die beiden Schleifen n*(n+1)/2 mal durchlaufen.
Schleife 1 : n Ausführungen
Schleife 2 und 3 : n*(n+1)/2 Ausführungen
LZ(n) = n * n*(n+1)/2 € O(n^3)
Angenommen der Code lautet
for(j=0, j < n^2; j++)
for (k = 0, k < j; k++)
sum = sum+1
dann werden die beiden Schleifen n^2*(n^2+1)/2 mal durchlaufen.
Schleife 1 : n Ausführungen
Schleife 2 und 3 : n^2*(n^2+1)/2 Ausführungen
LZ(n) = n * n^2*(n^2+1)/2 € O(n^5)
d)
Schleife 1 : n Ausführungen
Schleife 2: n/3 Ausführungen
LZ(n) = n * n/3 = n^2/3 € O(n^2)