For the following recurrence: T(n) = 3T(n/4) + cn^2
The book I am using provides the following Recurrence Tree to find the complexity of this Recurrence:
If a step-by-step explanation for the construction of this Recurrence Tree could be provided, it would be much appreciated.
At each step, they're recursively replacing each $T(\blacksquare)$ with an appropriate copy of the tree from part (b). So each row has 3 times as many items in it as the row above it, and the number of rows is going to be based on how many times you can divide $n$ by 4 before you get to 1 (or in the range of it).