DryRun
AlgorithmsCourseCompare
DryRun
AlgorithmsCourseCompareGitHubLinkedIn

© 2026 DryRun. Built by Aditya Pandey.

AlgorithmsAdvancedStrassen's Matrix Multiplication
Advancedadvanceddivide-and-conquermatrixfast-algorithms

Strassen's Matrix Multiplication

Strassen partitions matrices into 2x2 blocks and computes seven recursive multiplications instead of eight, reducing asymptotic complexity to approximately O(n^2.81).

Complexity

Best
O(n^2.81)
Average
O(n^2.81)
Worst
O(n^2.81)
Space
O(n^2)

Implementation

// Strassen skeleton (square matrices, power-of-two size)
vector<vector<int>> addM(const vector<vector<int>>& A, const vector<vector<int>>& B){
    int n=A.size(); vector<vector<int>> C(n, vector<int>(n));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];
    return C;
}
vector<vector<int>> subM(const vector<vector<int>>& A, const vector<vector<int>>& B){
    int n=A.size(); vector<vector<int>> C(n, vector<int>(n));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) C[i][j]=A[i][j]-B[i][j];
    return C;
}

How It Works

1.Block Decomposition

Split A and B into A11/A12/A21/A22 and B11/B12/B21/B22.

2.Seven Products

Compute P1..P7 and reconstruct C blocks with additions/subtractions.

3.Trade-off

Better asymptotic time but higher constants and numerical sensitivity in practice.

Related Algorithms

LayoutGridMatrix Chain MultiplicationArrowUpDownMerge Sort

Test Your Knowledge

Quiz coming soon for this algorithm.

Back to all algorithms