Divide and Conquer?
Divide and Conquer?
- Assume matrices of size 2nī2n
- Multiplications: M(n) = 8M(n/2), M(1)=8
- Additions: A(n) = 8A(n/2)+n2
- M(n) = 8lg n = nlg 8 = n3
- Additions are also Q(n3), but point is moot
- Can we reduce the 8 multiplications in the base equations