Following on from supervisions this week, I was wondering about Examples Sheet 1, #1 and the running time of dynamic programming. I found this wiki article about Matrix chain multiplication
https://en.wikipedia.org/wiki/Matrix_chain_multiplication
The article explains how a naive application of dynamic programming results in a run-time that is exponential in the number of matrices, $n$, which is very slow and impractical. That is what I asked about in the examples sheet. However, by remembering partial results, so that the same thing is not computed more than once, the run-time can be reduced to $O(n^3)$. By reducing the problem to one of polynomial triangulation the running time can be made $O(n\log n)$.
https://en.wikipedia.org/wiki/Matrix_chain_multiplication
The article explains how a naive application of dynamic programming results in a run-time that is exponential in the number of matrices, $n$, which is very slow and impractical. That is what I asked about in the examples sheet. However, by remembering partial results, so that the same thing is not computed more than once, the run-time can be reduced to $O(n^3)$. By reducing the problem to one of polynomial triangulation the running time can be made $O(n\log n)$.
