Big O of zfill in Python?

Question

I have a question: what is the big O or time complexity of Python's built-in function zfill? I don't know where to find this information.

Answer 1

Python zfill implementation lives here.

Here is is relatively apparent that the implementation is primarily composed of an allocation and memset/memcpy, with the rest being very simple addition/subtraction.

The big-O of these operations are platform/implementation/circumstance driven and often not that depended on the length of the string (They might happen instantaneous. They might allocate a new page for heap and request access to extra memory from an external services taking a few second). But for your purposes I would act like it is O(n), where n is the size of the resulting string, since that is probably what memset/memcpy have (as discussed here alloc is not really measurable).

But in truth, you probably shouldn't worry about this, since there is nothing you can do to change it. A manually implementation would certainly be slower.