La respuesta va con spoilers. Quienes lean, si no pensaron el ejercicio dejen de leer :)
La implementación concreta efectivamente construye una matriz de tamaño 
. Es un buen argumento decir que para ésta implementación particular el tiempo es 
en el peor caso (para cualquier entrada se da ese tiempo, de hecho). Pero, ¿se puede implementar el algoritmo sin crear las matrices?
Sí, se podrían usar otras estructuras. Lo importante que vean en este ejercicio es que esa discusión no importa. En tiempo, G-S es en peor caso por una cuestión fundamental del algoritmo, y no de una implementación concreta: la cantidad de proposiciones que se hacen.
. Es un buen argumento decir que para ésta implementación particular el tiempo es en el peor caso (para cualquier entrada se da ese tiempo, de hecho). Pero, ¿se puede implementar el algoritmo sin crear las matrices?Sí, se podrían usar otras estructuras. Lo importante que vean en este ejercicio es que esa discusión no importa. En tiempo, G-S es
en peor caso por una cuestión fundamental del algoritmo, y no de una implementación concreta: la cantidad de proposiciones que se hacen.