מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/זמן הריצה של הכפלת שרשרת מטריצות תחת Memoization/שאלה

אנא וודא את הנוסחות הבאות בזמן הריצה של הכפלת שרשרת מטריצות תחת memoization:

1. $\displaystyle T'(i,j)=\Theta (j-i+1)$ (נזכר ש$\displaystyle T'(i,j)$ מוגדרת כזמן שאורכת Min-Time(i, j) בהנחה שכ"א מהקריאות הרקורסיביות היא $\displaystyle O(1)$).
2. $\displaystyle T(1,n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]$.
3. $\displaystyle T(1,n)=\Theta (n^{3})$.