matrix multiplication algorithm time complexity

Question

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]

Solution 1

The naive algorithm, which is what you've got once you correct it as noted in comments, is O(n^3).

There do exist algorithms that reduce this somewhat, but you're not likely to find an O(n^2) implementation. I believe the question of the most efficient implementation is still open.

See this wikipedia article on Matrix Multiplication for more information.

Solution 2

Using linear algebra, there exist algorithms that achieve better complexity than the naive O(n³). Solvay Strassen algorithm achieves a complexity of O(n^2.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(n^2.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.

Solution 3

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.

Solution 4

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)

View more solutions