> For the complete documentation index, see [llms.txt](https://soveet-nayak.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soveet-nayak.gitbook.io/algorithms/divide-and-conquer/strassens-matrix-multiplication.md).
# Strassen's Matrix multiplication
Given two square matrices A and B of size n x n each, find their multiplication matrix. \
\&#xNAN;***Naive Method*** \
Following is a simple way to multiply two matrices. \
| void multiply(int A\[]\[N], int B\[]\[N], int C\[]\[N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C\[i]\[j] = 0;
for (int k = 0; k < N; k++)
{
C\[i]\[j] += A\[i]\[k]\*B\[k]\[j];
}
}
}
}
|
| -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| |
Time Complexity of above method is O(N^3). \
***Divide and Conquer*** \
Following is simple Divide and Conquer method to multiply two square matrices. \
1\) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram. \
2\) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh. \
\
In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N2) time. So the time complexity can be written as
```
T(N) = 8T(N/2) + O(N2)
From Master's Theorem, time complexity of above method is O(N3)
which is unfortunately same as the above naive method.
```
***Simple Divide and Conquer also leads to O(N3), can there be a better way?*** \
In the above divide and conquer method, the main component for high time complexity is 8 recursive calls.
The idea of **Strassen’s method** is to reduce the number of recursive calls to 7. Strassen’s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the above diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.\
**Time Complexity of Strassen’s Method** \
Addition and Subtraction of two matrices takes O(N^2) time. So time complexity can be written as \
```
T(N) = 7T(N/2) + O(N2)
From Master's Theorem, time complexity of above method is
O(NLog7) which is approximately O(N2.8074)
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://soveet-nayak.gitbook.io/algorithms/divide-and-conquer/strassens-matrix-multiplication.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.