[algorithm] matrix multiplication algorithm time complexity

I came up with this algorithm for matrix multiplication. I read somewhere that matrix multiplication has a time complexity of o(n^2). But I think my this algorithm will give o(n^3). I don't know how to calculate time complexity of nested loops. So please correct me.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

This question is related to algorithm time-complexity matrix-multiplication

The answer is


The standard way of multiplying an m-by-n matrix by an n-by-p matrix has complexity O(mnp). If all of those are "n" to you, it's O(n^3), not O(n^2). EDIT: it will not be O(n^2) in the general case. But there are faster algorithms for particular types of matrices -- if you know more you may be able to do better.


In matrix multiplication there are 3 for loop, we are using since execution of each for loop requires time complexity O(n). So for three loops it becomes O(n^3)


Using linear algebra, there exist algorithms that achieve better complexity than the naive O(n3). Solvay Strassen algorithm achieves a complexity of O(n2.807) by reducing the number of multiplications required for each 2x2 sub-matrix from 8 to 7.

The fastest known matrix multiplication algorithm is Coppersmith-Winograd algorithm with a complexity of O(n2.3737). Unless the matrix is huge, these algorithms do not result in a vast difference in computation time. In practice, it is easier and faster to use parallel algorithms for matrix multiplication.


Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to matrix-multiplication

How to get element-wise matrix multiplication (Hadamard product) in numpy? Difference between numpy dot() and Python 3.5+ matrix multiplication @ Matrix multiplication using arrays Matrix Multiplication in pure Python? matrix multiplication algorithm time complexity how does multiplication differ for NumPy Matrix vs Array classes?