3 ms·
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 exponen
by robinhouston 8y ago
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.
- madcaptenor 8y agoNo, 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.)
- romwell 8y ago* linear in input, not size of the input :)
- madcaptenor 8y agoYou're right. I stand corrected.
- ychen306 8y agoYou 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)
- romwell 8y agoOK, 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.