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)?
What is n?
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).