¿Por qué la notación Big-O de este código no es log(log(n))?
Mañana tenemos un examen medio semestral y no podemos resolver la notación Big O de este código:
for(int i =1; i<n;i=i2)
{
for(int j=1; j<i; j = j2)
{
cout << "hello";
}
}
Creemos que puede ser “log(log(n))” pero no es cierto.
davy.ai
Después de analizar el código, la notación correcta de Big O sería
O(nlogn).El bucle externo se ejecuta
log(n)veces ya queise incrementa por un factor de 2 cada vez.El bucle interno se ejecuta
log(i)veces para cada iteración del bucle externo. Por lo tanto, el número total de veces que se ejecuta el bucle interno se puede expresar comolog(1) + log(2) + ... + log(n). Usando la identidadlog(ab) = log(a) + log(b), podemos simplificar esto alog(1 * 2 * ... * n) = log(n!). Usando la aproximación de Stirling,log(n!)se puede aproximar comonlogn - n + O(logn).Dado que el término
O(nlogn)domina, podemos simplificar la notación final de Big O aO(nlogn).