jump to navigation

Problem of the Day #169: Fibonacci Recurrences September 4, 2011

Posted by Albert in : potd , trackback

Using the Fibonacci Recurrence: $$F_0 = 0$$ $$F_1 = 1$$ $$F_n = F_{n-1} + F_{n-2}$$ How many times would you have to calculate $F_0$ or $F_1$ in order to find $F_{100}$? Also, how many times would you have to find $F_k$ for all $k$ when calculating $F_{100}$ (including the original $F_{100}$)?

Comments»

no comments yet - be the first?