Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
O Kalk Aufgabe
Folgendes Fragment ist gegeben :
final int k = …;
void f2(int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n/2; j++) {
if(i < k) {
Rumpf();
}
}
}
}
Die Aufgabe ist es nun das O-Kalkül dafür zu bestimmen. Die Lösung soll O(n) sein. Aber warum ? (Aufgabe aus WS 2007 : Aufgabe 9 a , zweites Fragment)
Die äußere Schleife wird wegen der if-Bedingung k(Konstante) mal ausgeführt, die innere n/2 mal.
O((k/2) * n) = O(n). Konstanten fallen weg.