Buenas, en el monitoreo para hacer la parte a pusimos el ejemplo de que la preferencias de los hombres sea
w1 w2 w3 para todos los hombres y las mujeres igual, hombre 1, 2 ,3 para todas las mujeres, entonces al calcular la cantidad de iteraciones esta queda igual a n(n+1)/2 siendo n la cantidad de hombres y mujeres (para el ejemplo usamos n=3).
Ahora, me cuesta ver por qué concluimos que eso nos da el omega, por qué no nos da el O?
acota los tiempos por encima. La notación 
, por debajo. Si ustedes encontraron una instancia que tarda tiempo 
, lo que pueden deducir es que el peor caso (que puede haber sido alcanzado con esa instancia que mostraron, o podría ser algo peor que no encontraron) tarda por lo menos eso.
con este argumento, porque podría existir un caso aún peor que podría tardar, por ejemplo un tiempo, tiempo 
(en el libro se prueba que no, pero eso es otra cuestión).
.