time-complexity

What is the time complexity of printing an integer?

I'm trying to understand the time complexity of a simple program that prints an integer. The python code looks like this:

n = 123456789
print(n)

I initially thought the complexity was O(1) since printing seems like a constant time operation. However, considering that n has mm digits, where m≈log⁡10(n)+1, it seems like printing each digit would take O(1) time, making the overall complexity O(m).

Given that m is the number of digits and is proportional to log⁡10(n), does this mean the time complexity is actually O(log⁡n)?

Could someone clarify whether the time complexity of printing an integer is O(1) or O(log⁡n)? If it's O(log⁡n), could you explain why in more detail?

Thank you!

Solution

  • The time complexity of printing integers in Python is O(log(n)^2), which can be seen from observing the time taken for str(n) for increasingly large n (Python 3.10.12 on Linux):

    $ python3 -m timeit -s 'n=1<<512' 'str(n)'
100000 loops, best of 5: 1.4 usec per loop
$ python3 -m timeit -s 'n=1<<1024' 'str(n)'
50000 loops, best of 5: 4.46 usec per loop
$ python3 -m timeit -s 'n=1<<2048' 'str(n)'
10000 loops, best of 5: 15.9 usec per loop
$ python3 -m timeit -s 'n=1<<4096' 'str(n)'
5000 loops, best of 5: 59.5 usec per loop
$ python3 -m timeit -s 'n=1<<8192' 'str(n)'
1000 loops, best of 5: 231 usec per loop

    Every time we double the size of n (doubling log(n)), the amount of time goes up by a factor of 4, which fits O(log(n)^2) almost perfectly.

    Why is it O(log(n)^2)? Producing each digit of the output involves dividing the number by 10 repeatedly. Division itself requires time proportional to the length of the number. Hence, we do O(log(n)) divisions, each of which costs O(log(n)) time.

    We can get a much better time complexity by using hexadecimal representation rather than using decimal. Since numbers are internally represented in binary, converting to hexadecimal does not require division; instead, each group of four bits is directly translated to the corresponding hexadecimal digit. Thus, we expect the time complexity of hexadecimal output to be O(log(n)), and this is exactly what we see:

    $ python3 -m timeit -s 'n=10**150' 'hex(n)'
500000 loops, best of 5: 325 nsec per loop
$ python3 -m timeit -s 'n=10**300' 'hex(n)'
500000 loops, best of 5: 554 nsec per loop
$ python3 -m timeit -s 'n=10**600' 'hex(n)'
200000 loops, best of 5: 1.04 usec per loop
$ python3 -m timeit -s 'n=10**1200' 'hex(n)'
100000 loops, best of 5: 2 usec per loop
$ python3 -m timeit -s 'n=10**2400' 'hex(n)'
50000 loops, best of 5: 3.9 usec per loop

    Here, I’m using powers of ten of comparable size to the binary numbers above to avoid just outputting long strings of zeros.

    The quadratic complexity of converting large numbers to and from decimal led to Python introducing limits on the length of decimal numbers in Python 3.11 to avoid denial-of-service attacks; see https://docs.python.org/3/library/stdtypes.html#int-max-str-digits for more details. That document also references an algorithm which has subquadratic complexity. The exact complexity of that algorithm depends on the division algorithm used. It isn’t used in Python, as it is quite a bit more complicated to implement, but it is implemented in GNU GMP (accessible via the gmpy package).