Analysis of Strassen
Analysis of Strassen
- Only 7 multiplications are used
- Will work with matrices, because associative property is not used
- Multiplications: M(n) = 7M(n/2), M(1) = 7
- Additions: A(n) = 7A(n/2)+18(n2/4)
- M(n) = 7lg n = nlg 7 = n2.81
- Additions are also Q(n2.81)
- First algorithm to break the n3 “barrier”