Given two square matrices A and B of size n x n each, find their multiplication matrix.
Strassen's Matrix Multiplication is based on the Divide and Conquer Methodology.
In divide and conquer approach, the problem is divided into smaller but similar sub-problems and then each problem is solved independently. When we keep on dividing the subproblems into even smaller sub-problems, we may reach a stage where no more division is possible. Those smallest possible sub-problem are solved individually and the solution of all sub-problems is finally merged/combined in order to obtain the solution of an original problem.
Divide and Conquer algorithm solves a problem using following three steps.
1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers
