Question

The time complexity recurrence for Strassen's Matrix multiplication is

• A. $T\left(n\right)=4T\left(n/2\right)+n^2$
• B. $T\left(n\right)=8T\left(n/2\right)+n^2$
• C. $T\left(n\right)=7T\left(n/2\right)+n$
• D. $T\left(n\right)=7T\left(n/2\right)+n^2$

Answer 1

The correct option is D $T\left(n\right)=7T\left(n/2\right)+n^2$

Strassen's Approach needs 7 Multiplications and 18 Additions/ Subtractions.