[Solved]: Using the Master theorem on a recurrence with non-constant a

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