On the Linear Time Algorithm For Finding Fibonacci Numbers

You're viewing a comment by Richie and its responses.

Richie Permalink
July 07, 2009, 12:34

Without reading your analysis it's clear that LnearFibonacci computes all the fib numbers up to "n", and then throws all but the last number away. Next time it recomputes the same numbers again, so of course you get complexity O(n^2).

If the function filled an array then computation would be linear and only one call would be required.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.