Es O (n log n). La razón:
Suponga que “j” toma los pasos “k” para llegar a n. Es entonces cuando las condiciones del bucle se vuelven falsas y salimos del bucle. Cuando j alcanza n , el nuevo valor de j dado por j = 2 * j es (2 ^ k) .
Pero como j <n podemos presumir con seguridad (2 ^ k)> n.
Tome el registro en ambos lados:
Entonces la inecuación se convierte en k> log n
- ¿Dónde se utilizan los algoritmos criptográficos en nuestras aplicaciones diarias?
- Cómo hacer que esta declaración se entienda a un chico de 18 años
- ¿Cuál sería un buen método o algoritmo para predecir el ganador de una carrera de caballos, dada una gran cantidad de información sobre las carreras de caballos?
- ¿Cuáles son los algoritmos de correspondencia de gráficos de última generación?
- ¿Cómo funciona la recursividad en el árbol de búsqueda binaria en orden? ¿Cómo se pueden explicar las llamadas recursivas, sin resumirlas como llamadas de pila?
eso significa que k es una función que es mayor que log n. Por lo tanto, sabemos que al menos k tiene la forma Omega (log n) como k upperbounds log n .
Sin embargo, ahora tenemos que considerar el ciclo i en la ecuación. I loop se ejecuta hasta n, que es al menos n veces. Por lo tanto, k tiene que ir hacia arriba i y log n para retener su forma Omega. Pero no lo hace. Por lo tanto, k <i log n, que no es más que k <n log n.
Y esto reduce la ecuación a k = O (n log n), que es la complejidad temporal del algoritmo.
