Recurrence of splitting a matrix array?

by mymemesarespiciest   Last Updated September 11, 2019 22:05 PM

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

Answers 1

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

September 11, 2019 21:32 PM

Related Questions

Time complexity analysis for recurrence relation

Updated July 28, 2015 16:39 PM

tail-recursion over recursion for general use

Updated May 26, 2015 23:02 PM