If we have a matrix of nxn, what is the recurrence of splitting it into 4 equal parts of size (n/2)*(n/2)?

I thought it would be 4T(n/4) since we are splitting it into a 1/4 of the original size, but I saw from my book there is a similar problem (matrix multiplication) where the recurrence they got from splitting two matrices into 8 (n/2)*(n/2) matrices was 8T(n/2).

Would it be kT(n/2) or kT(n/4)?

New contributor
mymemesarespiciest is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

put on hold as unclear what you're asking by gnat, Doc Brown, BobDalgleish, Bart van Ingen Schenau, Jörg W Mittag Sep 14 at 7:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.


What is n?

  • If n is the number of elements in the matrix, then after splitting it into four pieces every piece will contain n/4 elements.
  • If n is the number of rows/columns in the matrix so that overall size is n×n, then after splitting the matrix into four pieces each piece will have n/2 rows/columns.

The correct approach depends purely on your definition for n in the problem you are investigating. It seems that since you have a n×n matrix and not n elements, you should model this as kT(n/2).

  • In this case, n is the number of rows and column. I appreciate the response. – mymemesarespiciest Sep 11 at 21:35
  • Going off that, if I had T(n) = kT(n/2) + f(n), would f(n) have to follow the same definition as the recurrence? For example, if I iterated through every row, would that be n because I went through each row or n^2 because I had to go through every element? Just trying to get this completely straight in my head. I was thinking it is n^2, but I'm not sure. – mymemesarespiciest Sep 11 at 21:37
  • @mymemesarespiciest well, are you iterating through every row or every element? I have no idea what you're actually doing. But your analysis seems correct so far. – amon Sep 11 at 21:44
  • For the problem I am working on, I am iterating through every row, but every element in the row. In other words, the entire nxn matrix. – mymemesarespiciest Sep 11 at 21:45

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