The standard DP solution for matrix-chain multiplication runs in
AO(n²)
BO(n³)
CO(2^n)
DO(n log n)
Answer & Solution
Correct answer: B. O(n³)
The DP fills an n × n table where each cell tries O(n) split points. Total time is O(n²) cells × O(n) per cell = O(n³). The other options describe different running times: O(n²) is the cell count (not the per-cell work), O(2^n) is exponential (avoided by DP), O(n log n) is too low for this problem.
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