Solución:
¿Cuál es la complejidad temporal de bin (n) en python, donde n es un número decimal (entero)?
¿Cuánto tiempo se tarda en convertir de decimal a binario?
No hay conversión para el número n de decimal a binario porque la representación interna ya es binaria. Un valor entero se representa como una matriz de 64-bit valores (por ejemplo, si el valor es menor que 2^64 - 1 entonces la matriz contiene un elemento). Por lo tanto, para mostrarlo en forma binaria, es necesario imprimir desde el bit más alto al más bajo.
Si observa el código fuente de bin() o más específicamente macro #define WRITE_DIGITS(p) enlace aquí, verá el siguiente bucle:
for (i = 0; i < size_a; ++i) {
...
}
size_a representa un tamaño de número a (tamaño de la matriz de enteros de 64 bits) para el que se debe encontrar una representación binaria.
Entonces, dentro del for bucle hay un while en que bits de i-ésimo dígito de a se extraen y guardan en una representación de cadena p:
...
do {
...
cdigit = (char)(accum & (base - 1));
cdigit += (cdigit < 10) ? '0': 'a' - 10;
*--p = cdigit;
...
} while (...);
...
El bucle interno se ejecuta hasta que se extraen todos los bits del dígito actual. Después de esto, los bucles externos se mueven al siguiente dígito y, por lo tanto, todos los bits se extraen nuevamente del bucle interno. Etcétera.
Pero el número de iteraciones es igual a un número de bits en la representación binaria de un número dado. n cual es log(n). Por tanto, la complejidad temporal de bin() por un número n es O(log(n))