Using a recursion tree to obtain an algorithm classification with n^2 time

Question

I'm having trouble getting the classification of this recurrence relation using a recursion tree.

$$T(n) = 3T(n/2) + n^2$$

I have the tree written out correctly (I hope):

                                         n^2
                                      /   |   \
                                     /    |    \
                              (n/2)^2  (n/2)^2  (n/2)^2
                        /   |   \      /  |  \     /   |    \
                       /    |    \    /   |   \   /    |     \
               (n/4)^2   (n/4)^2 ...      ...         ...    (n/4)^2
                                         ...
                                         ...
              T(1) T(1) ... ... ... ... ... ... ... ... ... ... T(1) T(1)

And for each "level" I have the running times:

                                Level         Time
                                  0            n^2
                                  1            3(n/2)^2
                                  2            9(n/4)^2
                                 log_2{n}      ???

So I'm having trouble getting the time for the base case at level $log_2{n}$, and after that I'm unsure of what I'm supposed to do with all the different times to get the overall running time. Do I add them all up? Do I just take the running time of the $log_2{n}$ level?

Thank you for any help you can give.

Answer 1

At each level, the number of nodes triples and $n$ is cut in half. Extending the pattern in your table, we see that at level $k$, the time is $3^k(\tfrac{n}{2^k})^2 = (\tfrac{3}{4})^kn^2$. At the second-to-last level, we have $k = \log_2 n - 1$, which corresponds to the term $(\tfrac{3}{4})^{\log_2 n - 1}n^2$. At the last level when $k = \log_2 n \iff n = 2^k$, the base case kicks in. Assuming that $T(1) = c$ for some constant $c$, this level has running time $3^kT(1) = 3^{\log_2 n}c = cn^{\log_2 3}$.

Adding up all the levels, we observe that (other than the last level) we have a finite geometric series with initial term $a = n^2$, common ratio $r = \frac{3}{4}$, and a total of $N = \log_2 n$ terms. By applying the usual formula, we obtain: \begin{align*} T(n) &= [n^2 + (\tfrac{3}{4})n^2 + (\tfrac{3}{4})^2n^2 + \cdots + (\tfrac{3}{4})^{\log_2 n - 1}n^2] + cn^{\log_2 3} \\ &= \frac{n^2(1 - (\frac{3}{4})^{\log_2 n})}{1 - \frac{3}{4}} + cn^{\log_2 3} \\ &= 4n^2\left(1 - \frac{3^{\log_2 n}}{4^{\log_2 n}}\right) + cn^{\log_2 3} \\ &= 4n^2\left(1 - \frac{n^{\log_2 3}}{n^{\log_2 4}}\right) + cn^{\log_2 3} \\ &= \left(4n^2 - 4n^2 \cdot \frac{n^{\log_2 3}}{n^2}\right) + cn^{\log_2 3} \\ &= 4n^2 + (c - 4)n^{\log_2 3} \\ \end{align*} Notice that since $2 = \log_2 4 > \log_2 3$, it follows that $T(n) = \Theta(n^2)$.