Beim ersten Beispiel hast du diese Variable y, die mit n initialisiert wird. Solange y > 0 ist, wird eine for-Schleife, die immer y Durchläufe hat abgearbeitet. Nach jedem Loop halbiert sich der Wert in y.
Das heißt, wenn n = 6 und damit y = 6 ist, dann machst du 6 Durchläufe und y = 6/2=3 ... also machst du dann im nächsten Schritt nur noch 3 Durchläufe usw.
Allgemein: n + n/2 + n/4 + n/8, wobei jeder Summand die jeweilige Anzahl an Durchgängen der for-Schleife beschreibt, beginnend bei n ... und da bei der Laufzeitbetrachtung die "unwichtigen" Teile i. d. F. Summanden wegfallen bleibt am Ende nur noch n (O(n)) übrig.
Betrachtung aus einer anderen Perspektive: Im Endeffekt konvergiert diese Summe (n + n/2 + n/4 ...) gegen 2n, also ist deine Laufzeit O(2n) und damit O(n).
Schüler, Punkte: 455