Nochmals O-Notation

[buzz_lightzyear]

Hallo nochmal,

ich hab gleich noch eine Frage zu einem anderen Beispiel und zwar gehts hier um die Fibonacci-Folge (rekursiv).

Die Rekursionsgleichung dazu lautet:

T(n)=O(1) + T(n - 1) + T(n - 2)=                           //Rekursionsgleichung, alles klar

=O(1) + O(1) + T(n - 2) + T(n - 3) + T(n - 2) 

Hier hab ich ein kleines Verständnisproblem und zwar:

Ich bin hier einen Rekursionsschritt tiefer, sprich ich habe (n-1) für n in die erste Gleichung eingesetzt -> ok!

Aber woher kommt das letzte T(n - 2)? Das kann ich nicht nachvollziehen... :-(

Jemand einen Tipp für mich? :-)

Thx & Lg

buzz