Next we determine the cost at each level of the tree. Each level has three times more nodes than the level above, and so the number of nodes at depth i is 3ⁱ. Because subproblem sizes reduce by a factor of 4 for each level we go down from the root, each node at depth i, for i = 0, 1, 2,..., log₄ n - 1, has a cost of c(n/4ⁱ)². Multiplying, we see that the total cost over all nodes at depth i, for i = 0, 1, 2,..., log₄ n - 1, is 3ⁱ c(n/4ⁱ)² = (3/16)ⁱ cn². The last level, at depth log₄ n, has nodes, each contributing cost T (1), for a total cost of , which is .

Now we add up the costs over all levels to determine the cost for the entire tree:

This last formula looks somewhat messy until we realize that we can again take advantage of small amounts of sloppiness and use an infinite decreasing geometric series as an upper bound. Backing up one step and applying equation (A.6), we have

Thus, we have derived a guess of T (n) = O(n²) for our original recurrence T (n) = 3T (⌊n/4⌋) Θ(n²). In this example, the coefficients of cn² form a decreasing geometric series and, by equation (A.6), the sum of these coefficients is bounded from above by the constant 16/13. Since the root's contribution to the total cost is cn², the root contributes a constant fraction of the total cost. In other words, the total cost of the tree is dominated by the cost of the root.

In fact, if O(n²) is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The first recursive call contributes a cost of Θ(n²), and so Ω (n²) must be a lower bound for the recurrence.

Now we can use the substitution method to verify that our guess was correct, that is, T (n) = O(n²) is an upper bound for the recurrence T (n) = 3T (⌊n/4⌋) Θ(n²). We want to show that T (n) ≤ dn² for some constant d > 0. Using the same constant c > 0 as before, we have

T(n)	≤	3T(⌊n/4⌋) cn2
	≤	3d⌊n/4⌋2 cn2
	≤	3d(n/4)2 cn2
	=	3/16 dn2 cn2
	≤	dn2,

where the last step holds as long as d ≥ (16/13)c.