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)
 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.

  • $\begingroup$ Duplicate? $\endgroup$ – Raphael Jul 25 '17 at 17:25
  • $\begingroup$ Note that O(n²) and O(n³) are not contradictory statements. Are you after $\Theta$? $\endgroup$ – Raphael Jul 25 '17 at 17:26
  • 1
    $\begingroup$ 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. $\endgroup$ – 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)$

  • 1
    $\begingroup$ This is not the way the code works currently. It's only $2U(R/2,C)$ or only $2U(R,C/2)$. $\endgroup$ – Yuval Filmus Jun 25 '17 at 14:21
  • $\begingroup$ My algorithm is now correct? @Moti, can you edit your answer? $\endgroup$ – Logic Jun 25 '17 at 14:22

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)$.

  • $\begingroup$ I know this. I would like to see how to to compute complexity for my algorithm. Because it is hard to me. $\endgroup$ – Logic Jun 25 '17 at 15:30
  • $\begingroup$ I have just shown you how to compute the complexity for your algorithm. $\endgroup$ – Yuval Filmus Sep 23 '17 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.