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.
result = 0;
for (int i=0; i<n/2; i += 5) {
for (int j=0; j<10; ++j) {
result += a[i+j];
}
}
return result;
for (int x : a) {
for (int i=0; a[i]!=x; ++i) {
foo(i);
}
}
result = 0;
for (int i=0; i<a.length; ++i) {
for (int j=i; j>0; j/=2) {
result += a[j];
}
}
return result;
function bar(int n):
if (n <= 0)
return 0
else
return n + bar(n-2)