Fibonacci numbers Recursive definition: ifn=o fn=l Fn1+ F. ifn≥2 0112358132134 Naive recursive algorithm: Q(on) (exponential time ), where o=(1+ 5)/2 s the golden ratio Day 4 Introduction to Algorithms L3.13Day 4 Introduction to Algorithms L3.13 Fibonacci numbers Recursive definition: Fn = 0 if n = 0; Fn–1 + Fn–2 if n ≥ 2. 1 if n = 1; 0 1 1 2 3 5 8 13 21 34 L Naive recursive algorithm: Ω(φn) (exponential time), where φ = is the golden ratio. (1+ 5)/2