Mazdak Farrokhzad edited b) Dynamic programming.tex  about 10 years ago

Commit id: 4fd046364246e833f144e2acf2b0c8daf536c68f

deletions | additions      

       

From the outset, it is obvious that the memory complexity is $\mathcal{O}(n)$  The cost of initializing the memory is: $n$  The  algorithm will do $n$ fills. It will also do: $i - 1$ lookup for each $i$, so the total complexity is:  $T(n) = n + n + \displaystyle\sum_{i=0}^{n} [i-1]$