Question:
What is the time complexity to find the optimal parenthesization of a chain of \(n\) matrices using Dynamic Programming (Matrix Chain Multiplication)?
डायनामिक प्रोग्रामिंग का उपयोग करके \(n\) मैट्रिक्स की एक श्रृंखला के इष्टतम गुणन क्रम को खोजने की समय जटिलता क्या है?
Options:
- \(O(n^3)\)
- \(O(n^2)\)
- \(O(2^n)\)
- \(O(n \log n)\)
- \(O(n^3)\)
- \(O(n^2)\)
- \(O(2^n)\)
- \(O(n \log n)\)
Correct Answer: a)
Explanation:
Matrix Chain Multiplication requires computing entries for a table of size \(n \times n\), where each cell takes \(O(n)\) time to compute minimum across \(k\). Thus, total time complexity is **\(O(n^3)\)** (Option a).
मैट्रिक्स चेन गुणन में \(n \times n\) टेबल को भरने और प्रत्येक सेल के लिए \(O(n)\) गणना के कारण कुल समय जटिलता **\(O(n^3)\)** होती है (विकल्प a)।