Trying to solve recurrence $T(n)=3T(n/3) + 3$

Question

I'm trying to solve the following recurrence without using the Master Theorem:

$$T(1)=1;$$

$$T(n)=3T(n/3) + 3$$

---

My attempt:

$T(n) = 3T(n/3) + 3$

$ = 3(3T(n/9) n/3)) + 3)$

$ = 9T(n/9) + 9$

$ = 9(3T(n/27 + n/9)) +9$

$ = 27T(n/27) + 9$

$ ...$

I know this is wrong but I'm stuck here. Thanks.

Answer 1

Writing out the first few terms, we get:

$$T(1) =1, T(3) = 6, T(9) = 21, T(27) = 66, T(81) = 201$$

Using this, we can see that $T(n) \approx2n$, so we make the ansatz that $T(n) = an + b$

Applying this to the recurrence relation gives us: $$\begin{align*}an + b &= 3\left(a\frac{n}{3} + b\right) + 3\\an + b &= an + 3b + 3\\2b &= -3\\b &= \frac{-3}{2}\end{align*}$$

Finally, applying the boundary condition $T(1) = 1$: $$\begin{align*}a + b &= 1\\a -\frac{3}{2} &= 1\\a &= \frac{5}{2}\end{align*}$$

Hence:

$$T(n) = \frac{5}{2}n - \frac{3}{2}$$

Answer 2

A change of argument turns this into a linear difference equation with constant coefficients. Let $n=3^k$. Then $$T(n)=T\left(3^k\right)=a_k=3T(n/3)+3=3T\left(3^{k-1}\right)+3=3a_{k-1}+3$$ The solution to the homogeneous equation, $a_k=3a_{k-1}$ is $a_k=C\cdot3^k$ and there is a constant solution, $a_k=-3/2$ to the actual equation. Thus the general solution is $$a_k=C\cdot3^k-\frac32$$ Applying the initial condition, $T(1)=a_0=C-3/2=1$, we have $$a_k=T(3^k)=\frac52\cdot3^k-\frac32$$ So $T(n)=\frac52n-\frac32$, for $n$ a power of $3$. For other $n$ we don't have an initial condition.

Answer 3

This recurrence only makes sense when repeatedly dividing $n$ by three eventually yields 1; that is, when $n$ is a power of three. So let's start by assuming that $n=3^m$. Then we may restate the problem as:

$$ \begin{eqnarray} T(3^0)&=&1 \\ T(3^m)&=&3T(3^{m}/3)+3 &=& 3T(3^{m-1})+3 \end{eqnarray} $$ or $$T(3^m)-3T(3^{m-1})-3=0$$ I'll point out that this is an order 1 linear recurrence relation in $m$, and that dictates that form of the result. But instead of just pulling a formula out of thin air and solving for some coefficients, I'll demonstrate a method to actually derive the formula: using ordinary generating functions.

Let $f(x)=T(3^0)+T(3^1)x+T(3^2)x^2+\cdots$ be the ordinary generating function for the sequence $\{T(3^m)\}$. We want to combine some multiples of this power series so that the the coefficients of the combination will satisfy the recurrence relation. To do this, we calculate:

$$ \begin{eqnarray} f(x)&=&T(3^0)&+&T(3^1)x&+&T(3^2)x^2&+&T(3^4)x^3&+&\cdots \\ -3xf(x)&=&0&-&3T(3^0)x&-&3T(3^1)x^2&-&3T(3^2)x^3&+&\cdots \\ \frac{-3}{1-x}&=&-3&-&3x&-&3x^2&-&3x^3&+&\cdots \\ \end{eqnarray} $$

Ok, I'll admit I did pull that last formula (for an infinite geometric series) out of thin air. Adding these together, we have:

$$ \begin{eqnarray} f(x)-3xf(x)-\frac{3}{1-x} &=& -3 + T(3^0)&+&[T(3^1)-3T(3^0)-3]x&+&[T(3^2)-3T(3^1)-3]x^2&+&\cdots \\ &=& -2 &+& [0]x &+& [0]x^2 &+&\cdots \end{eqnarray} $$ So that $$ \begin{eqnarray} [1-3x]f(x)&=&-2 +\frac{3}{1-x} \\ f(x)&=&\frac{-2}{1-3x}+\frac{3}{(1-x)(1-3x)} \\ &=&\frac{-2}{1-3x}-\frac{\frac{3}{2}}{1-x}+\frac{\frac{9}{2}}{1-3x} & \textrm{(partial fraction decomposition)} \\ &=&\frac{\frac{5}{2}}{1-3x}-\frac{\frac{3}{2}}{1-x} \\ &=&[\frac{5}{2}-\frac{3}{2}]+[\frac{5}{2}\cdot 3^1-\frac{3}{2}\cdot1^1]x+[\frac{5}{2}\cdot3^2-\frac{3}{2}\cdot1^2]x^2+\cdots \end{eqnarray} $$

Matching coefficients yields $$ \begin{eqnarray} T(3^m) &=& \frac{5}{2}\cdot3^m-\frac{3}{2} \\ T(n) &=& \frac{5}{2}n-\frac{3}{2} \end{eqnarray} $$

Answer 4

$$T(n)=3T\left(\frac{n}{3}\right)+3=3\left(3T\left(\frac{n}{3^2}\right)+3\right)+3=3^2T\left(\frac{n}{3^2}\right)+3^2+3$$Continuing so on....... $$T(n)=3^kT\left(\frac{n}{3^k}\right)+3^k+3^{k-1}+..........+3^2+3\tag{1.}$$ Let $n=3^k$ then $T\left(\frac{n}{3^k}\right)=T(1)=1$ ,putting this in eq (1) :- $$T(n)=3+3^2+3^3+...........+3^k+3^k=\frac{3(3^k-1)}{2}+3^k=\frac{3(n-1)}{2}+n=5\frac{n}{2}-\frac{3}{2}$$ i.e. $$T(n)=\theta(n)$$