On the Linear Time Algorithm For Finding Fibonacci Numbers

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

steve Permalink
July 07, 2009, 19:33

No technically is it exponential. This is a common problem used to trip up CS grad students during their qualifying exam. When finding the complexity of an algorithm, you must consider the number of steps with respect to the input. The input is log(n) and the number of steps in the for loop is n, hence the algorithm is exponential with respect to the input.

This is why the naive primality test:

isPrime(int n) {
 for (i=2;i<=n/2;i++) {
   if (n%i==0) return false;
 }
 return true;
}

fails to be O(n). Although long suspected to be in P, primality was not classified as such until the recent discovery of the AKS primality test.

See: http://en.wikipedia.org/wiki/Pseudo-polynomial_time for more info

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.