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 k*T(n/2) or k*T(n/4)?

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 *k*T(*n*/2).

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger