Step 1: Recursion Tree Structure

The recursion tree has:

• Root node cost: $\mathrm{\Theta }(n^2)$
• Two child nodes: $T\left(\frac{n}{4}\right)$ and $T\left(\frac{n}{2}\right)$
• This pattern continues until reaching small subproblems

Step 2: Cost at Each Level

Level 0 (Root):

$$\text{Cost}=n^2$$

Level 1:

$$\text{Left child}={\left(\frac{n}{4}\right)}^2=\frac{n^2}{16}$$

$$\text{Right child}={\left(\frac{n}{2}\right)}^2=\frac{n^2}{4}$$

$$\text{Total cost}=\frac{n^2}{16}+\frac{n^2}{4}=\frac{5n^2}{16}$$

Level 2:

$$\text{Left-left}={\left(\frac{n}{16}\right)}^2=\frac{n^2}{256}$$

$$\text{Left-right}={\left(\frac{n}{8}\right)}^2=\frac{n^2}{64}$$

$$\text{Right-left}={\left(\frac{n}{8}\right)}^2=\frac{n^2}{64}$$

$$\text{Right-right}={\left(\frac{n}{4}\right)}^2=\frac{n^2}{16}$$

$$\text{Total cost}=\frac{21n^2}{256}$$

General Pattern:

$$\text{Cost at level }k=n^2{\left(\frac{5}{16}\right)}^k$$

Step 3: Summing Over All Levels

The total cost is an infinite geometric series:

$$T(n)=n^2+\frac{5n^2}{16}+\frac{25n^2}{256}+\cdots$$

With first term $a=n^2$ and common ratio $r=\frac{5}{16}$

Since $|r|<1$, the series converges to:

$$T(n)=\frac{a}{1-r}=\frac{n^2}{1-\frac{5}{16}}=\frac{16n^2}{11}$$

Step 4: Asymptotic Upper Bound

The root cost ($n^2$) dominates the entire series:

$$T(n)=O(n^2)$$