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)