Lösung
bearbeitet von 1unitedpower> 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. Für eine korrekte Lösung ist `O(n)` deshalb optimal.