Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Question

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$?

I've drawn the tree for the recurrence and found a sequence: $n + 2n + \frac{8}{3}n+\frac{32}{9}n+\frac{128}{27}n+\frac{512}{81}n$...

But I'm not sure 1. how to write this sum in $\sum$-form and, more formally, how I can prove the tight asymptotic bound for the original recurrence.

Answer 1

By the master theorem, since $f(n)=0$, $$T(n)=\Theta(n^{\log_{3/2}3})$$ If $f(n)=n$ or even $n^2$, this result would still hold, since $O(f(n))<\log_{3/2}3\approx 2.7$.

Answer 2

Recall the recursion tree. The "weight" of every node is constant and reading out the recurrence we see a regular tree where every node has a fan-out $3$ and a sub-problem of size divided by $3 / 2$ at each level. From the root to the bottom, the $i$-th level has an overall weight equals $\mathcal{O}(1)3^i$ and the tree height is $\log_{3/2} n$. The sum below yields the following geometric sums with ratio $3$.

$$T(n) = \sum_{i = 0}^{\log_{3/2} n - 1} \mathcal{O}(1)3^i = \mathcal{O}(1) \cdot \frac{3^{\log_{3/2} n} - 1}{3 - 1} \in \mathcal{O}(n^{\log_{3/2} 3}) = \mathcal{O}(n^{2.71})$$

You can verify this result by applying the master theorem. In fact, this is precisely the upper bound given by the master theorem.