Strassen’s Matrix Multiplication Algorithm

Strassen’s Algorithm is an algorithm for matrix multiplication. It is faster than the naive matrix multiplication algorithm. In order to know how, let’s compare both of these algorithms along with the their implementation in C++.

Suppose we are multiplying 2 matrices A and B and both of them have dimensions n x n. The resulting matrix C after multiplication in the naive algorithm is obtained by the formula:

for i = 1, …, n and j = 1, …, n

The C++ implementation of this formula is:

int** multiply(int** A, int** B, int n) { int** C = initializeMatrix(n); setToZero(C…