Question:
What is the time complexity to multiply two \(n \times n\) matrices using Strassen’s matrix multiplication algorithm?
स्ट्रैसेन के मैट्रिक्स गुणन कलनविधि का उपयोग करके दो \(n \times n\) मैट्रिक्स को गुणा करने की समय जटिलता क्या है?
Options:
- \(O(n^{\log_2 7}) \approx O(n^{2.807})\)
- \(O(n^3)\)
- \(O(n^2 \log n)\)
- \(O(n^{2.5})\)
- \(O(n^{\log_2 7}) \approx O(n^{2.807})\)
- \(O(n^3)\)
- \(O(n^2 \log n)\)
- \(O(n^{2.5})\)
Correct Answer: a)
Explanation:
Strassen’s algorithm computes the product of two \(n \times n\) matrices by recursively performing 7 matrix multiplications of size \(n/2\), giving recurrence \(T(n) = 7T(n/2) + O(n^2)\), which solves to \(O(n^{\log_2 7}) \approx O(n^{2.807})\).
स्ट्रैसेन कलनविधि 8 के स्थान पर केवल 7 गुणन करता है: \(T(n) = 7T(n/2) + O(n^2)\), जिससे समय \(O(n^{\log_2 7}) \approx O(n^{2.807})\) हो जाता है।