Previous: Analyse von while-Schleifen
Up: O-Notation
Next: Korrektheit und Terminierung
Beispiel:
Die Laufzeit von
beträgt:
Offenbar gilt:
für ein
(denn
würde zu
führen).
Gesucht ist also ein
, so dass für große
gilt:
Teile durch
:
![$\Rightarrow$](img107.gif)
-
.
Für
und
geht
.
![$\Rightarrow$](img107.gif)
-
(gemäß Formel
)
![$\Rightarrow$](img107.gif)
- Das rekursive Fibonacci-Programm hat die Laufzeit
, wobei
der Wert des Inputs ist, nicht seine
Länge!
Previous: Analyse von while-Schleifen
Up: O-Notation
Next: Korrektheit und Terminierung