Ejercicios de práctico (2021)

Hola Tomas.

El bloque rojo no es O(1), es $\Omega$(1), es decir, que voy a invertir al menos tiempo constante en cada iteración del while.

Dependiendo de la implementación podría llegar a invertir más tiempo por iteración, pero la cota inferior $\Omega$(1) se sigue cumpliendo.

Como en peor caso voy a iterar del orden de n²  veces invirtiendo al menos un tiempo constante en cada iteración, entonces en peor caso el while me va a llevar al menos un tiempo del orden de n², que es la noción de $\Omega$(n²), acotar inferiormente el comportamiento del tiempo de ejecución de mi algoritmo.

Luego puedo encontrar una implementación que me permita alcanzar esa cota inferior, o puedo encontrar otras implementaciones que no puedan alcanzarla e inviertan un tiempo de orden mayor en cada iteración del algoritmo (por ejemplo usando listas), pero nunca voy a encontrar una implementación que me permita invertir un tiempo de orden menor en cada iteración, por lo que la cota inferior sobre el tiempo de ejecución del peor caso se cumple para toda implementación.

Avisame si ahora quedó un poco más claro, sino lo seguimos viendo.

Saludos!