On the Linear Time Algorithm For Finding Fibonacci Numbers

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

David Permalink
July 07, 2009, 13:06

Corey, Richie: I believe you are incorrect. The following is a naive O(n^2) algorithm for calculating the nth fibonacci number:

def fib(n):
if n == 0 or n == 1:
return n
else: return fib(n-1) + fib(n-2)

However, the OP's algorithm simply performs n additions to find the nth fibonacci number -- there is no recursion. To work out [LinearFibonacci(x) for x in xrange(1,n)] would be O(n^2), but LinearFibonacci(n) itself is just O(n) (counting additions as constant time).

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.