3 ms·
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 l
by madcaptenor 8y ago
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.)
- 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)