What is the complexity of str() function in Python3?

I have to create a function respecting an O(n) complexity and to do that i want to use the str() function.

Can someone explain me if :

str(1000)

Is this code O(1) or O(4) because of the 1+0+0+0 ?

Answer

As can be seen from the source code, the implementation of int.__str__ has runtime complexity of O(m*n) where m is the number of binary digits and n is the number of decimal digits. Since for an integer i the number of digits in an arbitrary base b is given by log(i, base=b) and logarithms in different bases differ only by a constant, the runtime complexity is O(log(i)**2), i.e. quadratic in the number of digits.

This can be verified by running a performance test:

import perfplot

perfplot.show(
    setup=lambda n: 10**n,
    kernels=[str],
    n_range=range(1, 1001, 10),
    xlabel='number of digits',
)

The quadratic time complexity in the number of digits is also mentioned in the issue for CVE-2020-10735:

[…] A huge integer will always consume a near-quadratic amount of CPU time in conversion to or from a base 10 (decimal) string with a large number of digits. No efficient algorithm exists to do otherwise.