Multiplying A(10×100) · B(100×5) · C(5×50): the cost difference between (AB)C and A(BC) is
Aboth cost the same; matrix multiplication is commutative
B(AB)C is twice as expensive as A(BC)
C(AB)C costs 7500 ops, A(BC) costs 75000 ops, a 10x difference
Dneither parenthesisation is valid because dimensions don't match
Answer & Solution
Correct answer: C. (AB)C costs 7500 ops, A(BC) costs 75000 ops, a 10x difference
(AB) is 10×5, costing 10·100·5 = 5000; then (AB)C costs 10·5·50 = 2500; total 7500. (BC) is 100×50, costing 100·5·50 = 25000; then A(BC) is 10·100·50 = 50000; total 75000. 10x difference. Same answer matrix, very different work. Matrix multiplication is associative (the answer matches) but not commutative.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for