Computing fibonacci numbers Naive recursive squaring: F=nl5 rounded to the nearest integer n Recursive squaring: O(g n) time This method is unreliable, since floating-point arithmetic is prone to round-off errors Bottom-up Compute Fo, F1, F2,., Fn in order, forming each number by summing the two previous Running time:⊙(m) Day 4 Introduction to Algorithms L3.14Day 4 Introduction to Algorithms L3.14 Computing Fibonacci numbers Naive recursive squaring: Fn = φn/ 5 rounded to the nearest integer. • Recursive squaring: Θ(lg n) time. • This method is unreliable, since floating-point arithmetic is prone to round-off errors. Bottom-up: • Compute F0, F1, F2, …, Fn in order, forming each number by summing the two previous. • Running time: Θ(n)