# Time Complexity Of Bin() In Python

## 11 June 2018 - 1 answer

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 ?

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))`