Time complexity of bin() in Python

Question

What is the time complexity of bin(n) in Python, where n is a decimal number (integer)?

For example:

if n = 10, then bin(n) = 0b1010, so here what is happening behind the scenes? How much time does it take to convert from decimal to binary? What is Big O notation for this ?

Answer 1

what is the time complexity of bin(n) in python, where n is decimal number (integer) ?

How much time it takes to convert from decimal to binary ?

There's no conversion for number n from decimal to binary because the inner representation is already binary. An integer value is represented as an array of 64-bit values (for example, if the value is lower than 2^64 - 1 then the array contains one element). Hence, to show it in the binary form one needs to print out from the highest bit to the lowest one.

If you look into the source code for bin() or more specifically macro #define WRITE_DIGITS(p) link here, you will see the following loop:

for (i = 0; i < size_a; ++i) {
    ...
}

size_a stands for a size of number a (size of the array of 64-bit integers) for which a binary representation must be found.

Then, within the for loop there's a while in which bits from i-th digit of a are extracted and saved into a string representation p:

...
do {
    ...
    cdigit = (char)(accum & (base - 1));
    cdigit += (cdigit < 10) ? '0': 'a' - 10;
    *--p = cdigit;
    ...
} while (...);
...

The inner loop is executed until all the bits from the current digit are extracted. After this, the outer loops moves to the next digit and so all bits are extracted from it again the inner loop. And so on.

But the number of iterations is equal to a number of bits in the binary representation of a given number n which is log(n). Hence, the time complexity of bin() for a number n is O(log(n))

Answer 2

It is log(n). Think about the simple division, we divide the number by 2 until the remainder becomes 0 or 1 just like tree traversal.