Notación Big O con bucle interno especial.
Me gustaría tener ayuda en cuanto al análisis de la notación de Big O de lo siguiente.
Caso A:
El bucle interno solo se ejecuta una vez en el peor escenario.
for (int i = 0; i < nums.length; i++) {
if (i==nums.length-1 && nums[i] == 3){
for (int j = 0; j < nums.length; j++) {
print();
}
}
}
El peor escenario es un arreglo que termina en 3. ¿Es esto O(N) o O(N*N)?
La manera en que analizo esto es la siguiente:
- El bucle exterior se ejecuta N veces = 1(n)
- El bucle interno en el peor caso se ejecuta solo 1 vez = 1
Por lo tanto, n*1 = O(n), ¿estoy bien con el análisis?
¿Tiene sentido “n*1” o debería ser “n+1”?
Caso B:
El bucle interno siempre se ejecuta excepto si “i” es el primer elemento.
for (int i = 0; i < nums.length; i++) {
if (i!=0){
for (int j = 0; j < nums.length; j++) {
print();
}
}
}
La manera en que analizo esto es la siguiente:
- El bucle exterior se ejecuta N veces = n
- El bucle interno se ejecuta N-1 veces = n-1
Por lo tanto, n(n-1) = O(nn), ¿estoy bien con el análisis?
Estoy muy confundido con estos casos. ¡Gracias!
davy.ai
Para el caso A, tu análisis es correcto. El ciclo exterior se ejecuta N veces y el ciclo interior se ejecuta solo una vez en el peor escenario. Por lo tanto, la complejidad temporal es O(N). Es intercambiable escribirlo como n*1 o n+1 en términos de notación Big O, ya que tienen el mismo orden de magnitud.
Para el caso B, tu análisis es casi correcto. El ciclo exterior todavía se ejecuta N veces, pero el ciclo interior se ejecuta N-1 veces, no n-1 (n y N son lo mismo, solo con diferente capitalización). Por lo tanto, la complejidad temporal es en realidad O(N^2), como identificaste correctamente.