I am trying to solve the recurrence $T(n) = 3T(n/2)+n$ where $T(1) = 1$ and show its time complexity.
$n$ can be assumed to be a power of $2$.
So basically, I drew out the tree and found that:
the number of levels in the tree will be $h = \log_2 n+1$.
The number of leaves in the tree will then be $3^{h-1} = 3^{\log_2 (n) } = n^{\log_2 3}$
Now we can write the time formula..
$$T(n) = cn + c(3n/2) + c(9n/4) +\dots + cn(3^{h-2}/2(h-2)) + \Theta(n^{\log_2 3})$$
[stuck here, how should I formulate the summation? The summation diverges at infinity..]
$$T(n) = \Theta (n^{\log_2 3})$$
I can tell that the summation of the number of leaves is $n$ times some constant but I am not sure how to show that step.
Best Answer
Our time formula is: $$ T(n) = n + \frac{3}{2}n + \frac{3^2}{2^2}n + \cdots + \frac{3^{\log_2 n}}{2^{\log_2 n}}n $$ [As an aside, note that the last term is just $n^{\log_2 3}$.] Now this is a finite geometric series with initial term $a = n$, common ratio $r = \frac{3}{2}$, and $N = \log_2 n + 1$ terms. By applying the usual formula, we obtain: \begin{align*} T(n) &= \frac{n((\frac{3}{2})^{\log_2 n + 1} - 1)}{\frac{3}{2} - 1} \\ &= \frac{n(3^{\log_2 n + 1} - 2^{\log_2 n + 1})}{3(2^{\log_2 n}) - 2^{\log_2 n + 1}} \\ &= \frac{n(3(3^{\log_2 n}) - 2(2^{\log_2 n}))}{3(2^{\log_2 n}) - 2(2^{\log_2 n})} \\ &= \frac{n(3(n^{\log_2 3}) - 2n)}{3n - 2n} \\ &= \frac{n(3n^{\log_2 3} - 2n)}{n} \\ &= 3n^{\log_2 3} - 2n \\ \end{align*}
which belongs to $\Theta(n^{\log_2 3})$.