# Time Complexity Of Bin() In Python

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

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

## Related Questions

- → What are the pluses/minuses of different ways to configure GPIOs on the Beaglebone Black?
- → Django, code inside <script> tag doesn't work in a template
- → React - Django webpack config with dynamic 'output'
- → GAE Python app - Does URL matter for SEO?
- → Put a Rendered Django Template in Json along with some other items
- → session disappears when request is sent from fetch
- → Python Shopify API output formatted datetime string in django template
- → Can't turn off Javascript using Selenium
- → WebDriver click() vs JavaScript click()
- → Shopify app: adding a new shipping address via webhook
- → Shopify + Python library: how to create new shipping address
- → shopify python api: how do add new assets to published theme?
- → Access 'HTTP_X_SHOPIFY_SHOP_API_CALL_LIMIT' with Python Shopify Module