Hola,
Estoy intentando hacer el ejercicio del título. La respuesta ha de ser \( log^2 n \) donde \( n\in{\mathbb{Z}_+} \).
Para ello yo he escrito un algoritmo, que no es mas que el habitual
\( c \;vector\;\;\;\;, k=0\;\;\;\;\;\;\;\;\;
while \;n\; distinto \;de \;1,0
\left\{{k=k+1\;\;\;\;\;\;\;\;
mod n/2=c[k]\;\;\;\;\;\;\;\;\;\;
n=n/2\;\;\;\;\;\;\;\;\;\;\;
}\right\}\;\;\;\;\;\;
c[k+1]=n \)
C es el vector que va a dar como resultado el número en binario. Sabemos que el while va a repetirse a sumo \( \left<{log_2n}\right> \) (parte entera del log). El problema es calcular la complejidad de \( mod n/2 \), que es tomar el resto de la división \( n/2 \). No sé si esta complejidad sería la misma que dividir \( n/2 \). A lo mejor es \( o(dividir)+o(restar) \), por el teorema de la división entera.
Además, he demostrado que la complejidad de multiplicar dos números binarios de \( k \) y \( l \) cifras es \( o(k) \) si k es mayor que l. Pero no sé la complejidad de dividir. ¿Es la misma que multiplicar?
Un saludo.