# Using the Master theorem on a recurrence with non-constant a

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.

-
Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! – Raphael Jan 25 at 9:47

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.
Let's say that $T(n) = 3^n T(n/3) + C$. Then $T(n) \geq 3^n T(n/3)$ and $T(n) - C \geq 3^n (T(n/3) - C)$. This shows that in order to estimate the rate of growth of $T(n)$, it is enough to solve the recurrence $S(n) = 3^n S(n/3)$ with appropriate initial values (different for the lower and upper bounds). You haven't specified what the interpretation of $n/3$ is for $n$ which are not divisible by 3, but for powers of 3 we definitely have \begin{align*} S(n) &= 3^n S(n/3) = 3^{n+n/3} S(n/9) = \cdots = 3^{n+n/3+n/9+\cdots+3} S(1) \\ &= 3^{n(1 + 1/3 + 1/9 + \cdots + 1/(n/3))} S(1) \\ &= 3^{(3/2)n - (3/2)} S(1) \\ &= \Theta(3^{(3/2)n}). \end{align*} We conclude that, at least for powers of 3, $T(n) = \Theta(3^{(3/2)n})$.