You're replying to a comment by Corey.

July 07, 2009, 12:56

yes, LinearFibonacci() is O(n), but you run it m number of times which means the total computation is O(mn) time. And on each run of LinearFibonacci() m = n so that's O(n^2). Why should that be a surprise?

Also, Richie is correct: if you cached your previous results, it would be O(n). You've only come up with an O(n^2) algorithm for a problem that could be solved in O(n) time.

Reply To This Comment

(why do I need your e-mail?)

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

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

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