alt Hacker NewsReally it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
Really it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
Big O analysis never implies size in bits. It's just often done. In this case, n is just the numerical value of the input, so I don't think this is correct.