marceloarenassaavedra
commented
3 years ago Perdón por lo lento de la respuesta, se me había pasado esta pregunta.
De todas maneras me parece que es bueno responderla.
La pregunta de la interrogación 1 del año pasado está correcta. En la pregunta se pedía demostrar que el algoritmo funciona en tiempo polinomial en |w_1| + |w_2|, lo cual se obtiene demostrando que el algoritmo funciona en tiempo O(|w_1| * |w_2|) como fue dicho en clases, y considerando que |w_1| * |w_2| <= (|w_1| + |w_2|)^2.
Saludos!
Hola, tengo una consulta, el año pasado se preguntó por el siguitente algoritmo
Sin embargo, tengo mis dudas sobre si la complejidad esperada es efectivamente esa, o debería ser O(|w1||w2|), que es la que vimos en clases con programación dinamica y bottom-up (me imagino que si ya que dice tiempo polinomial, asi que supongo que es un typo).