-1
$\begingroup$

I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct.

By no means, am I a genius, but I was wondering if you guys could point out where this algorithm lacks.

The algorithm:

Base case:
     MCM(A) = 0;
     MCM(AB) = nrow(A) * ncol(A) * ncol(B)
Otherwise:
     MCM(AB....JK) = min(MCM(B...K) + cost_of_mul(A, B...K),
                     MCM(A...J) + cost_of_mul(A...J, K),
                     MCM(AB) + MCM(C...K) + cost_of_mul(AB, C...K),
                     MCM(A...I) + MCM(JK) + cost_of_mul(A...I, JK));

where MCM is a nxn matrix that stores the minimum number of scalar products needed for the sequence from i to j (MCM[i][j])

The rationale behind this is that each grouping takes care of at least two matrices, and that is being handled when considering the minimum.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ It's already known that this can be done in time $O(n\log n)$ (see the Wikipedia page). I guess your angle is that your algorithm trades simplicity for efficiency. However, verifying research isn't something we do here: our scope is answering specific questions and "Is my research correct?" is too open-ended. I suggest you try to prove that your algorithm (a) produces the correct answer and (b) does so in $O(n^2)$ steps. Testing isn't enough. $\endgroup$ – David Richerby Oct 13 '16 at 10:24
1
$\begingroup$

Your algorithm has lower complexity than the straightforward standard version of the dynamic programming solution, because it scans only a (strict) subset of the subproblems it needs to consider.

Say there are $n$ matrices at some point. Your algorithm checks five specific parenthetizations: between first and second, between penultimate and last, etc. It's possible that the optimal parenthetization is between the element at $\left\lfloor \frac{n}{2} \right\rfloor$ and $\left\lfloor \frac{n}{2} \right\rfloor + 1$, for example, but your algorithm doesn't check that.

It's possible that you tested it on a few test cases and it worked, because the optimal sub-solutions might appear in the restricted subsets which you check.

Of course, you could expand your solution to check for all parenthetizations. In that case, though, you'll reach the regular conclusion for the (straightforward version of the) dynamic programming solution for this problem - filling up the $n^2$ entries needed for the solution takes $\Theta\left(n^3\right)$ time.

|cite|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.