|
|
|
|
|
|
by NAR8789
1328 days ago
|
|
|
Because it only takes log(n) digits to represent n. 9 is 1 digit, takes 9 steps. 99 is 2 digits, takes 99 steps. 999 is 3 digits, takes 999 steps. An input d decimal digits long takes O(10^d) steps. The runtime is exponential in the "size of the input", because the size of the input is usually taken to be the length of the binary or decimal representation of the number rather than the magnitude of the number. |
|
|