Time complexity of bin() in Python
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))