On the Linear Time Algorithm For Finding Fibonacci Numbers

You're viewing a comment by John Tantalo and its responses.

July 07, 2009, 15:11

Why have you compared the running time of Fib(n) to Fib(n)? There's no reason why this should give you any information about the complexity of the function. You must have meant to compare the running time of Fib(n) to n, which should be linear. It's no surprise that you found a quadratic relationship since the running time is linear in n and Fib(n) is quadratic in n, so Fib(n) is quadratic with respect to the running 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.