Problem Detail: I am trying to solve the following equation using master’s theorem. $T(n) = 3^n T(frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what my $a$ value is I don’t think its just 3.
Asked By : Steph
Answered By : Tom van der Zanden
This is not solvable using (only) the Master Theorem. It’s not in the correct form. The Master Theorem only applies when there’s a constant in front of the $T(n/b)$, and $3^n$ is definitely not a constant. You should try calculating a bound for $log(T(n))$ instead. Even though that won’t give a tight bound it will get you on the right track.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/52229 Ask a Question Download Related Notes/Documents
