# On the Linear Time Algorithm For Finding Fibonacci Numbers

You're replying to a comment by steve.

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

(Your twitter handle, if you have one.)

Type the word "lcd_147": (just to make sure you're a human)

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