1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Duplicate? $\endgroup$
    – Raphael
    Jul 25, 2017 at 17:25
  • $\begingroup$ Note that O(n²) and O(n³) are not contradictory statements. Are you after $\Theta$? $\endgroup$
    – Raphael
    Jul 25, 2017 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, 2017 at 19:50

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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, 2017 at 14:21
  • $\begingroup$ My algorithm is now correct? @Moti, can you edit your answer? $\endgroup$
    – Logic
    Jun 25, 2017 at 14:22
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2017 at 15:30
  • $\begingroup$ I have just shown you how to compute the complexity for your algorithm. $\endgroup$
    – Yuval Filmus
    Sep 23, 2017 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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