nicht angemeldet
Aber ist schon klar. Für die erste Binärziffer gibt's n/2 Durchläufe im Halbierer. Für die zweite sind es n/4, und so weiter, in Summe irgendwas zwischen n/2 und n.
Genau, die Summe n/2 + n/4 + n/8 + … konvergiert gegen n. Man kann sogar zeigen, dass dein Algorithmus hinsichtlich Laufzeit nicht zu überbieten ist. Wenn es einen Algorithmus mit geringerer Laufzeitschranke gäbe, würde er nicht alle Ziffern der Eingabe lesen, das heißt, er würde manche Eingaben nicht unterscheiden können und falsche Ergebnisse liefern (da die zu berechnende Funktion bijektiv ist). Für eine korrekte Lösung ist O(n) deshalb optimal.
Rolf B