Asymptotische Laufzeit von Pseudocode-Fragmenten

Question

Aufgabe

Bestimmen Sie die asymptotische Laufzeit der folgenden Pseudocode-Fragmente als Θ- Notation in Abhängigkeit von n. Sie können davon ausgehen, dass n eine Potenz von 2 ist

a) while (n >= 1) {
     for(i=1; i < n; i++){   
           print(i);
      }
      n=n/2;
      }

b)

int result=n;
for(i=1; i <= n*n; i++) {
     int value=i;
     for(j=1; j <= i; j++)
         result=result/2;
}
for(k=1; k <= n*n*n; k++)
     result=result*4;

Ansatz
a) Die while-Schleife wird durchlaufen wenn n größer oder gleich 1 ist. Für alle i, die kleiner als n sind, werden die i's addiert und ausgegeben. Die n werden dann jeweils halbiert.  Ich würde daher sagen, dass die Laufzeit linear ist, da kein expotentielles Wachstum oder sonstige logarithmische Faktoren dabei sind. (evtl. noch das mit dem halbieren?). Laufzeit daher Θ (n)

b) Es tut mir leid, ich habe nicht die geringste Ahnung, wie man hier vorzugehen hat. Vielleicht Θ (n log n), da im der oberen Scheife analog zu a) immer i's und j's linear aufaddiert werden, solange i kleiner als n² ist.. Und dann vllt. log (n), weil am Ende die Ergebnisse geteilt und später mit 4 multipliziert werden? :(

Answer 1

Für die Abschätzung der Laufzeit auf Basis der O-Notation spielt es keine Rolle, was in den Programmschleifen unabhängig von den Schleifenzähler passiert. Also z.B. "result=result*4;" fällt nicht ins Gewicht. Man möchte nur ein Maß dafür haben, um welchen Faktor sich die Laufzeit verlängert, wenn man die Schleifenzähler (hier n) vergrössert.

a)
O(n * log_2(n))

log_2(n) wegen n=n/2. Stünde da n = n -1, dann gilt O(n^2)

b)
1. for-Schleife
Summe k^2 (k=1 to n) = 1/6 * n * (n+1) * (2n+1)
also O(n^3), weil n^3 die grösste Potenz in dem obigen Ausdruck ist.

2. for-Schleife
ebenfall O(n^3)

O(n^3) + O(n^3) = O(n^3)