The number of distinct parenthesisations of n matrices is
An! ways (factorial growth)
B2^n ways (exponential growth)
Cn² ways (polynomial growth)
DCatalan C_{n-1}, ≈ Θ(4^n / n^1.5)
Answer & Solution
Correct answer: D. Catalan C_{n-1}, ≈ Θ(4^n / n^1.5)
Catalan numbers count parenthesisations: C_{n-1} for n matrices, with C_n ≈ Θ(4^n / n^1.5). Exponential in n. Trying every parenthesisation is hopeless for n > 20. n! is too fast-growing (would be for permutations), 2^n is too few, n² is far too few. DP collapses this to O(n³).
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