Matrix chain multiplication: Greedy approach some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.

The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.

The dynamic algorithm approach works at a time complexity of theta of N^3.

My question is, what is the runtime of this algorithm:

A= 5x2
B= 2x7
C= 7x3

1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).

*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.

*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.

2) Then divide the sequence to 2: (A)(B•C).
The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.

Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence. 

Is this algorithm optimal? 
It has to be better than N^3 (the usual algorithm)
Consider the product $ABC$, where


$A$ is $5\times 2$
$B$ is $2\times 3$
$C$ is $3\times 100$


Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products.

The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products.



Suppose that $A$ is $a\times b$, that $B$ is $b \times c$, and that $C$ is $c\times d$. There are two possibilities:


Compute $AB$ and then $(AB)C$: cost is $abc + acd = ac(b+d)$.
Compute $BC$ and then $A(BC)$: cost is $bcd + abd = bd(a+c)$.


The first option is preferable if
$$
\frac{b+d}{bd} &lt; \frac{a+c}{ac}
$$
or equivalently
$$
\frac{1}{b} + \frac{1}{d} &lt; \frac{1}{a} + \frac{1}{c}.
$$
For example, above we have $a = 5$, $b = 2$, $c = 3$, $d = 100$. Since
$$
\frac{1}{2} + \frac{1}{100} &lt; \frac{1}{5} + \frac{1}{3},
$$
the order $(AB)C$ is preferable.

Your decision procedure would prefer this order if $c &lt; b$, that is, if
$$
\frac{1}{b} &lt; \frac{1}{c}.
$$
Your condition misses the contribution of $a,d$.