¿Cómo puede alguien calcular la complejidad de este algoritmo?

Pregúntate a ti mismo las siguientes preguntas.

1. ¿Entiendes lo que hace el algoritmo y por qué funciona? Esto no es estrictamente necesario para determinar la complejidad, pero es un poco triste determinar la complejidad de un algoritmo que no entiendes.
2. ¿Cuáles son las entradas al algoritmo y cuál es el parámetro con respecto al cual estamos midiendo la complejidad? La complejidad siempre se mide en función del “tamaño” de entrada y desea asegurarse de saber cuál es el tamaño relevante. Si la entrada es una matriz lineal de elementos [math] n [/ math], el tamaño suele ser solo [math] n [/ math]. Si la entrada es un número, el tamaño suele ser el número de dígitos en la representación decimal o binaria del número.
3. ¿Qué tipo de complejidad buscamos: el mejor caso, el peor caso, el caso promedio? No importa mucho en este caso, pero es muy útil tener en cuenta las diferencias.
4. Finalmente, siga los bucles, bucles anidados, llamadas recursivas, etc. en el algoritmo e intente contar el número de pasos individuales que tienen lugar, en función de [math] n [/ math]. Esto a veces es complicado, pero esta instancia en particular no debería ser difícil para usted. Solo hay dos bucles, uno tras otro, y ninguno de ellos tiene pasos de magnitud internos que dependan de [math] n [/ math]. Entonces, ¿cuánto tiempo nos llevará pasar por el primer ciclo? ¿Cuánto tiempo llevará pasar el segundo?