Hacker News Reader

Something that people often seem to miss when talking about this sort of thing is that any correct exact algorithm to compute Fibonacci numbers must use exponential time and space — simply because the size of the correct exact output is exponential in the size of the input.

View on HN

OK, I see this response is getting downvoted. Here's a PSA on arithmetic.

The function n -> 2^n takes input of size O(log(n)) and returns output of size O(n).

Of course, n = 2^(log n), so our function takes exponential time/space in input size to simply write the output.

The Fibonacci function is like that.

Of course, discussions of complexity become cumbersome if you don't specify variables; that's why we talk about complexity in n of computing Fib(n).

Potato, potato anyway.

No, the size of the output is linear in the size of the input. (The Fibonacci numbers themselves grow exponentially, but the size of the output goes like the log of the number itself.)

* linear in input, not size of the input :)

You're right. I stand corrected.

You need O(log(n)) of bits to write down the input. So the output size is indeed exponential.

Size of input: O(log n)

Size of output: O(log(c^n)) = O(n)

Reply on news.ycombinator.com