-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.

$\endgroup$

closed as too broad by David Richerby, Evil, Raphael Oct 13 '16 at 13:47

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.

$\endgroup$

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