4 ms·
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)
by ychen306 8y ago
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)