Consultas Teórico/Práctico

Buenas, les dejo un resumen de los pasos que dimos en el práctico pasado sobre el análisis del tiempo de ejecución de un algoritmo (GS en este caso). Aunque intenté darle un tratamiento general,  tengan en cuenta el contexto de estos comentarios ya que se hacen muchas simplificaciones para lograr resumir.

Tenemos un problema P tiene un conjunto de instancias E. Suponemos que en E hay dos instancias particulares e₁ y e₂, y un algoritmo A que resuelve P (en este análisis no hablaremos de la complejidad de P, solo de A). Para el algoritmo A tenemos por ejemplo dos implementaciones I₁ e I₂.

1.  El libro probó que una  I₁ es O(n²) mostrando que para todas las instancias de E el tiempo de ejecución es O(n²). Por lo tanto A es O(n²) (logré encontrar una implementación que lo resuelve en ese tiempo para todo e perteneciente a E). Pero I₂ pordría ser Ω(n³) y no cambiaría la afirmación sobre A. 
2.  Si I₁ es O(n²) puede ser o(n²) también. Para probar que I₁ no es o(n²) hay que mostrar que es Ω(n²) . 
3.  En este punto no sabemos si  I₁ es Ω(n²) y tampoco sabemos si A es  Ω(n²) (sabemos que A es O(n²) , pero A  puede ser o(n²) también y por lo tanto la cota superior que probó el libro no ser la mejor).
4. En el práctico probamos que I₁ es Ω(n²), encontrando una instancia e₁ (o cierta estructura de instancia más precisamente) que hace que I₁ demore tiempo Ω(n²) . Podría sin embargo existir una e₂      que ejecutada en I₁ demore tiempo O(n), pero con eso no podemos afirmar que I₁ es O(n) (tendriamos que mostrarlo para todo e perteneciente a E, que de hecho no es cierto porque mostramos que no lo cumple e₁ ).
5. Al probar el tiempo Ω(n²) de I₁ no podemos estar seguro de la no existencia otra I₂ cuyo tiempo de ejecucion sea o(n²). Por lo anterior, en este punto todavia no sabemos si A es  Ω(n²).
6. Para probar que no va a existir otra I₂ que sea o(n²), en la parte b) del práctico se prueba que A es Ω(n²), usando los lemas del libro y una  instancia (se usó la misma e₁ pero puede ser otra).

Resumiendo, 

para que una implementacion sea O(n²) debe serlo para todas las instancias. 

Para que un algoritmo sea  O(n²)  alcanza con mostrar una implementacion  O(n²) .

Para que una implementación sea Ω(n²) alcanza con una instancia en la cual se demore Ω(n²).

Si un algoritmo es Ω(n²) debe serlo para todas las implementaciones posibles.