Sorry about the formatting. Had nothing but my cellphone!
Problem: Suppose this is an algorithm that runs in T(n) time, where T(n) is the following recurrence relation:
T(n) =
- $2T($$ \frac n3$$) + Θ(n), x > 2$
- $Θ(1), x ≤ 2$
Draw a tree and find the upper bound of T(n) in terms of n. Prove upper bound using Master Theorem.
My tried solution: The recursion tree that I ended up with;
Levels
- n
- $$ \frac n3 \frac n3 $$
- $$ \frac n9 \frac n9 \frac n9 \frac n9 $$
- …..
- $$(1) (1) … (1)$$
Work for each level.
- n
- $$ \frac n3 + \frac n3 = \frac 23n$$
- …
- k nodes. Since 2T, I got $2^k$ with work $$\frac {n}{3^k}$$, which
in the end would be $$ \left(\frac{2}{3}\right)^kn $$
Since there are $$log_3 (n)$$ levels, I ended up with $$n = \frac{n}{1-\frac{2}{3}} = 3n$$
EDIT: which in the end would be O(n).
When I try to prove this using Master Theorem, I can't for the life of me get it to work for any of the 3 cases.
For example, for case 1: I try to prove T(n) ≤ c*n and my end result is T(n) ≤ $$\frac 23n + n $$
Is my tree completely wrong or is my understanding of the master theorem wrong?
Any insight would be greatly appreciated, thanks!
Best Answer
Since the critical exponent is $\log_32$ and $f(n)$ is $\Omega(n^{\log_32})$, only the third (supercritical) case of the master theorem applies and we have to use the regularity condition $$2f(n/3)\le\color{blue}{\frac34}f(n)$$ on $f$ to get that $T(n)=\Theta(n)$ as desired.