So we I have the Matrix chain order algorithm which finds the optimal way in multiplying matrices. I see why it would have a run time of O(n^3) but having trouble proving its big-Omega(n^3). The algorithm is below Algorithm Matrix-Chain-Order(p)
1. n ← p.length − 1
2. for i ← 1 to n do
3. m[i, i] ← 0
4. for l ← 2 to n do
5. for i ← 1 to n − l + 1 do
6. j ← i + l − 1
7. m[i, j] ← ∞
8. for k ← i to j − 1 do
9. q ← m[i, k] + m[k + 1, j] + pi−1pkpj
10. if q < m[i, j] then
11. m[i, j] ← q
12. s[i, j] ← k
13. return s
O(n^3) is obvious since there are three loops which are nested and run O(n) times. How would I go about finding big-Omega(n^3)
Let's compute the number of inner loop iterations: $$\sum_{\ell = 2}^n\sum_{i = 1}^{n - \ell + 1}\sum_{k = i}^{i + \ell - 2} 1 = \sum_{\ell = 2}^n\sum_{i = 1}^{n - \ell + 1}(\ell - 1) = \sum_{\ell = 2}^n (n - \ell + 1)(\ell - 1)\\ = \sum_{\ell = 1}^n (n - \ell + 1)(\ell - 1) = \sum_{\ell = 1}^n (n\ell - \ell^2 - n + 2\ell - 1)\\ = \frac{n^2(n + 1)}{2} - \frac{n(n + 1)(2n + 1)}{6} - n^2 + n(n - 1) - n \sim \frac{n^3}{6} = \Omega(n^3).$$
Another approach is the following. You choose all triples $(i, k, j)$ such that $1 \le i \le k < j \le n$ and make some work for each triple. The number of such triples is the same as the number of triples $(i', k, j)$ such that $0 \le i' < k < j \le n$. It is the same as choosing subset of 3 elements from $\{\,0, 1, \ldots, n\,\}$. There are $\binom{n + 1}{3} \sim \frac{n^3}{6} = \Omega(n^3)$ of them.