0

My question is to solve the following using recurrence relation forward substitution then verify using mathematical substitution:

  • $T(n) = 2T(\frac{n}{3})$ for $n > 1$, where $n$ is a power of $3$
  • $T(1) = 3$

I'm not sure where to start as I'm used to using $T(1) = 3$

Thank you in advance

Warren Moore
  • 3,931
Dereck
  • 131
  • We have $T(3)=2T(1)=6$, $T(9)=2T(3)=12$, $T(27)=2T(9)=24$, and so on. In general, $T(3^n)=3\cdot 2^n$. – André Nicolas Apr 28 '13 at 18:58
  • For these kind of problems, a good idea is to write explicitly the first terms (e.g. $T(1), T(3), T(9)$) and see if you can identify the pattern. – baudolino Apr 28 '13 at 19:01

1 Answers1

0

The value of $T(1)$ need not worry us very much. Suppose that $T(1)=a$.

Then $T(3)=2T(3/3)=2T(1)=2a$.

Similarly, $T(9)=2T(9/3)=4a$, and $T(27)=2T(9)=8a$, and so on.

So in general $T(3^n)=2^n a$. In your particular example, you have $a=3$. So $T(3^n)=(3)(2^n)$.

André Nicolas
  • 507,029