algorithm design techniques algorithm such as strassen' algorithm does not significantly alter the problem we will considerso we will assume this performance bound what is the best way to perform the three matrix multiplications required to compute abcdin the case of four matricesit is simple to solve the problem by exhaustive searchsince there are only five ways to order the multiplications we evaluate each case belowr ( ((bc) ))evaluating bc requires , multiplications evaluating (bc) requires the , multiplications to compute bcplus an additional , multiplicationsfor total of , evaluating ( ((bc) )requires , multiplications for (bc)dplus an additional , multiplicationsfor grand total of , multiplications ( ( (cd)))evaluating cd requires , multiplications evaluating (cdrequires the , multiplications to compute cdplus an additional , multiplicationsfor total of , evaluating ( ( (cd))requires , multiplications for (cd)plus an additional , multiplicationsfor grand total of , multiplications ((ab)(cd))evaluating cd requires , multiplications evaluating ab requires , multiplications evaluating ((ab)(cd)requires , multiplications for cd , multiplications for abplus an additional , multiplications for grand total of , multiplications (((ab) ) )evaluating ab requires , multiplications evaluating (ab) requires the , multiplications to compute abplus an additional , multiplicationsfor total of , evaluating (((ab) )drequires , multiplications for (ab)cplus an additional , multiplicationsfor grand total of , multiplications (( (bc)) )evaluating bc requires , multiplications evaluating (bcrequires the , multiplications to compute bcplus an additional , multiplicationsfor total of , evaluating (( (bc))drequires , multiplications for (bc)plus an additional , multiplicationsfor grand total of , multiplications the calculations show that the best ordering uses roughly one-ninth the number of multiplications as the worst ordering thusit might be worthwhile to perform few calculations to determine the optimal ordering unfortunatelynone of the obvious greedy strategies seems to work moreoverthe number of possible orderings grows quickly suppose we define (nto be this number then ( ( ( and ( as we have seen in generalt(nn- ( ) ( ii= to see thissuppose that the matrices are an and the last multiplication performed is ( ai )(ai+ ai+ an then there are (iways to compute ( ai and ( -iways to compute (ai+ ai+ an thusthere are ( ) ( -iways to compute ( ai )(ai+ ai+ an for each possible