# Complexity of multiplying matrix

Let's consider the following algorithm to multiply squares matrix: A is a matrix of NxN. r_i, r_j defines interval of rows. For example r_i = 2, r_j=3 means the second and the third rows. c_i, c_j means the same as r_i, r_j but for columns. We assume that N = 2^s for some s.

mul(A, B, r_i, r_j, c_i, c_j){
if(r_i != r_j){
r_m = floor((r_i+r_j)/2)

mul(A, B,  r_i, r_m, c_i, c_j)
mul(A, B, r_m+1, r_j, c_i, c_j)
} else if(c_i != c_j){
c_m = floor((c_i+c_j)/2)
mul(A, B, r_i,r_j, c_i, c_m)
mul(A, B, r_i, r_j, c_m+1, c_j)
}else{
for i = 1 to N:
C[r_i][c_i] += A[r_i][i] * B[i][c_i]
}

}


And the most important:

Complexity of that algorithm takes: T(n) = 4T(n/2) + n = O(n^2)

And it is not correct. The correct answer is O(n^3). Why my computation is incorrect.

• – Raphael Jul 25 '17 at 17:25
• Note that O(n²) and O(n³) are not contradictory statements. Are you after $\Theta$? – Raphael Jul 25 '17 at 17:26
• I'm voting to close this question as off-topic because "please check my work" questions are unlikely ever to be useful to anyone except the asker. – David Richerby Sep 23 '17 at 19:50

Your calculation is not right... $$U(R,C) = 2U(\frac{R}{2},C)\textrm{ or } 2U(R,\frac{C}{2})\\ U(1,1) = O(n)$$
Basically, you have $N^2$ unique positions (which you drive your way down to recursively, rather than just looping) - for each of those you do a loop of O(N) so you have $O(N^3)$
• This is not the way the code works currently. It's only $2U(R/2,C)$ or only $2U(R,C/2)$. – Yuval Filmus Jun 25 '17 at 14:21
Your algorithm can be unrolled to the usual $O(N^3)$ matrix multiplication algorithm. If you open up all the recursive steps you will get a recursion tree whose $N^2$ leaves are of the form mul(A, B, r, r, c, c), each of which has running time $\Theta(N)$, for a total of $\Theta(N^3)$.