Sei c := (1 + sqrt(5)) / 2

Beh 1: F_n <= c^n 
Beweis durch Induktion.

Beh 2: F_n >= a*c^n für a = 1/c und n >= 1
Beweis durch Induktion.


Also: F_n in O(c^n) und F_n in Omega(c^n)
und somit 

F_n in Theta(c^n).


Um also abzuschaetzen, wie lange unser Algorithm für fib(50) 
braucht, könnten wir mal c^50 ausrechnen:

c^50 = 28,143,753,123.000046

28 Milliarden also. 

c^60 = 3,461,452,808,002.007


Die Laufzeit von fib(n) ist also Theta(c^n), also exponentiell.