alleryStart learning →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³).
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.