analysis of dynamic programming Matrix-Chain-Order

Question

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 (these are P(base)i-1
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)

You really have a variable named backquote? and what's pi-1pkpj? — Paul Hankin
– Paul Hankin, Commented Mar 16, 2017 at 2:23

Yola · Accepted Answer · 2017-03-16 12:42:38Z

1

To better understand question one could look here.

You need to compute elements of upper tirangular matrix. Let's look at these subdiagonals:

First subdiagonal, you need only 1 operation per its element, and the diagonal has n-1 element.
Second subidagonal you need 2 ops and it has n-2 elems.
...
For the last subdiagonal you need n-1 ops and it has 1 elem.

So, you have a summation i(n-i), for 0 < i < n. This summation can be split in two parts:

sum(in) = n(1+2+...(n-1)) = n(n/2)(n-1) = n^3/2-n^2/2
sum(i^2) = n(n+1)(2n+1)/6 = n^3/3+n^2/2+n/6

Now subtract and you will have n^3/6+...

So, it is Omega(n^3).

answered Mar 16, 2017 at 12:42

Yola

19.4k12 gold badges68 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

analysis of dynamic programming Matrix-Chain-Order

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related