Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
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
up vote 6 down vote accepted

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.

share|cite|improve this answer

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})$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.