Consider the problem of a chain <A1, A2, A3> of three matrices. Suppose that…
2014
Consider the problem of a chain <A1, A2, A3> of three matrices. Suppose that the dimensions of the matrices are 10 × 100, 100 × 5 and 5 × 50 respectively. There are two different ways of parenthesization : (i) ((A1 A2 )A3 ) and (ii) (A1 (A2 A3 )). Computing the product according to the first parenthesization is ________ times faster in comparison to the second parenthesization.
- A.
5
- B.
10
- C.
20
- D.
100
Attempted by 114 students.
Show answer & explanation
Correct answer: B
Answer: the first parenthesization is 10 times faster.
Compute cost for ((A1 A2) A3):
A1 (10×100) × A2 (100×5): 10*100*5 = 5,000 multiplications. Result is 10×5.
(Result 10×5) × A3 (5×50): 10*5*50 = 2,500 multiplications.
Total = 5,000 + 2,500 = 7,500 multiplications.
Compute cost for (A1 (A2 A3)):
A2 (100×5) × A3 (5×50): 100*5*50 = 25,000 multiplications. Result is 100×50.
A1 (10×100) × (Result 100×50): 10*100*50 = 50,000 multiplications.
Total = 25,000 + 50,000 = 75,000 multiplications.
Compare totals:
75,000 / 7,500 = 10, so the first parenthesization performs the computation 10 times faster.