Which statement describes Strassen's algorithm in terms of matrix multiplication complexity?

• A. Naive O(n^2); Strassen O(n^3)
• B. Naive O(n^3); Strassen O(n^3)
• C. Naive O(n^3); Strassen O(n^2)
• D. Naive O(n^3); Strassen O(n^log2 7) ≈ O(n^2.807)

Answer: (D)

Strassen's algorithm uses a divide-and-conquer approach to multiply two n×n matrices more efficiently than the straightforward method. In the naive approach, you perform n^3 scalar multiplications. Strassen splits each matrix into four n/2-by-n/2 blocks and cleverly combines seven products to form the result, instead of eight. This leads to the recurrence T(n) = 7 T(n/2) + O(n^2), which solves to T(n) = O(n^log2 7) ≈ O(n^2.807). So the description that matches is that the naive method is O(n^3) and Strassen runs in O(n^log2 7) ≈ O(n^2.807). The other possibilities would imply no improvement over the cubic time or an even faster than possible O(n^2) growth, which isn’t correct for Strassen.