Square terrain recurrence derivation You have a square terrain with area $A > 0$. You want to add information into the terrain. You want to subdivide the terrain into $4$ quadrants, process them individually, and assemble the results. To process, you divide a quadrant further until the sub-quadrants have area $\le A_0$, where you can then add information to the terrain- all in total of $i\cdot A$ time for $i > 0$. Each subdivision step results in each of the four quadrants containing $\frac13$ the area (as they may overlap). If $T(A)$ is the time to label a terrain of area $A$, what is its recurrence? I have an answer as $$4T(\frac{\frac{A}{A_0}}{3})+iA,$$ but I don't understand how it was derived. Can someone explain how each component of the problem relates to an addition in the final result? I understand the $4$ recursive calls, but not much after that.

This is an application of the master theorem. If you are looking for a proof, this link from wikipedia seems promising.