Hallo liebe Community,
ich bin neu im Informatikbereich und stoße gerade auf die Laufzeitanalyse.
Es ist eine Schleife gegeben, zu der wir eine Laufzeitanalyse mittels Vollständiger Induktion angeben sollen.
Mein Problem ist nun, dass ich überhaupt nicht weis wie ich anfangen soll.
Hier mal die Schleife:
int summe = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 2^i; j++) {
summe += 1;
}
}
Was da passiert verstehe ich soweit. Wir sollten im Voraus eine Vermutung abgeben, in welcher Laufzeitklasse dieses Programmfragment liegt.
Natürlich habe ich mich hinsichtlich der O-Notation schlau gemacht und vermute, dass es in der Laufzeitklasse O(n²) liegt.
Ich hab nur leider einfach keinen Schimmer, wie ich nun meine Vermutung mittels Vollständiger Induktion belegen kann.
Vielleicht kann mir ja einer von euch den richtigen Weg weisen.
Vielen Dank im Voraus für eure Aufmerksamkeit!
LG