Use the recursion tree method to determine an asymptotic upper bound for solution of the following recurrence:

Question

$$T(n) = 2T\left(\frac n4\right) + n$$ Use the substitution method to verify the upper bound found.

My recursion tree looks like this:

I got that the total Row sum is a geometric sequence and is equal to $n(1 + \dfrac12 + \dfrac14 + \dfrac18 + \cdots) = 2n$

Substitution method:

Am I doing this right? Is everything correct? Is $T(n) = \mathcal{O}(n\log n)$ ?

Answer 1

No. Why are you mixing the recursion tree method with the substitution method? $$T(n) = 2T\left(\frac n4\right) + n$$ This means that the height of the tree is $\log_4 n$ and the width of the tree is $2^{\log_4 n} =\sqrt{n}$. Assuming $T(1)$ takes constant time $k$, $$\begin{align}T(n) = k\cdot\sqrt{n} + \sum_{i = 0}^{\log_4{n}}\frac n{2^i} = k\cdot\sqrt{n} + n\cdot\sum_{i = 0}^{\log_4{n}}\frac 1{2^i} &= k\cdot\sqrt{n} + n\left(2 - \frac1{\sqrt{n}}\right)\\ &= k\cdot\sqrt{n} + 2n - \sqrt{n} \\ &= (k - 1)\sqrt{n} + 2n\end{align}$$ Since $n > \sqrt{n}$, $T(n)$ is $\Theta(n)$.

You can use the Master method (case III) for this, too.