Sé que el bucle 'while' externo se ejecuta log(n) veces. En el bucle 'for' tengo un problema. Intenté poner diferentes valores de 'n' y luego ver cuántas veces se ejecuta el bucle 'for', pero no obtengo una respuesta definitiva. Por ejemplo, con n=100, se ejecuta 13 veces, lo cual no es ni log(n) ni sqrt(n).
Se puede deducir una expresión para $j$ en cada iteración a partir de su fórmula recursiva.
Para hacer eso, nota que en la $l$-ésima iteración solo tienes que sumar $l$ al valor anterior de $j$. Sea $j_l$ el valor de $j$ en la $l$-ésima iteración.
Entonces \begin{align} j_l&=j_{l-1} + l\\ j_1 &=1 \end{align>
Es claro ahora que \begin{equation> j_l = \sum_{i=1}^l i = \frac{l(l+1)}{2} \end{equation> donde usamos esto para calcular la suma.
Ahora encuentra el valor de $l$ en el que finalizará el bucle interno \begin{align> j_l > n\\ \frac{l(l+1)}{2} > n \end{align>
Finalmente, sobreestimaremos $l$ para simplificar el procedimiento. Nota que esta sobreestimación no hace ninguna diferencia asintóticamente.
\begin{align> l^2 &> 2n\\ l &> \sqrt{2n} \end{align>
Entonces la complejidad general de este código es $\mathcal{O}(\sqrt{n}\log n)$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
