Gegeben sind ein paar (Pseudo-)Code-Stücke. Schätzen Sie jeweils die zugehörige Komplexitätsklasse ab und begründen Sie.

Tipp: Gehen Sie immer bottom-up vor. Bestimmen Sie zunächst die Komplexität der inneren Schleifenteile, dann die der äußeren.

Leiten Sie für diese Schleife die Worst Case Komplexität her. Gezählt wird die Anzahl der Feldzugriffe. Gegeben sei ein Integer-Array a der Länge $n>20$.

result = 0;
for (int i=0; i<n/2; i += 5) {
  for (int j=0; j<10; ++j) {
     result += a[i+j];
  }
}
return result;

Leiten Sie für diese Schleife Best Case und Worst Case her. Gezählt wird die Anzahl der Feldzugriffe. Gegeben sei ein Integer-Array a der Länge $n$. Nehmen Sie an dass foo(n) die Komplexität $\Theta(n)$ besitzt.

for (int x : a) {
  for (int i=0; a[i]!=x; ++i) {
    foo(i);
  }
}

Leiten Sie für diese Schleife die Worst Case Komplexität her. Gezählt wird die Anzahl der Feldzugriffe.

result = 0;
for (int i=0; i<a.length; ++i) {
  for (int j=i; j>0; j/=2) {
    result += a[j];
  }
}
return result;

Leiten Sie den Aufwand der folgenden rekursiven Funktion her. Gezählt werden Additionen und Subtraktionen (jeweils Kosten 1).

function bar(int n):
  if (n <= 0)
    return 0
  else
    return n + bar(n-2)

Code-Komplexität