¿Cuál es la complejidad temporal del siguiente código?
void fun(int n)
{
int j = 1, i = 0;
while (i < n)
{
// Some O(1) task
i = i + j;
j++;
}
}
La variable de bucle ‘i’ se incrementa en 1, 2, 3, 4,… hasta que i se vuelve mayor o igual que n.
El valor de i es x(x+1)/2 después de x iteraciones. Entonces, si el ciclo se ejecuta x veces, entonces x(x+1)/2 < n. Por lo tanto, la complejidad del tiempo se puede escribir como Θ(√n).
Este artículo es una contribución de Piyush Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA