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


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

  • $\begingroup$ Why the second line is $3(3T(n/9) n/3)) + 3)$ and not $3(3T(n/3)+3)+3$? $\endgroup$ – Phicar May 1 '16 at 2:14
  • $\begingroup$ Sorry I'm trying to figure out how to do this $\endgroup$ – Carlo May 1 '16 at 2:16
  • $\begingroup$ You must replace $k$ times the recurrence you have and see what should be $k$ in order to stop the recurrence and use $T(1)=1$. So, if $k=3$ $T(n)=3T(n/3)+3=3(3T(n/3^2)+3)+3=3(3(3T(n/3^3)+3)+3)+3=3^3T(n/3^3)+3+3^2+3^3$..so, do it in general for $k$ and the geometric sum will be helpful. $\endgroup$ – Phicar May 1 '16 at 2:23
  • $\begingroup$ I see. so what would Theta class would that be then? Theta(nlogn)? $\endgroup$ – Carlo May 1 '16 at 2:26
  • $\begingroup$ What expression do you have at the end? If you guess is that complexity, try to prove it by induction. $\endgroup$ – Phicar May 1 '16 at 2:31

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

  • $\begingroup$ Perfect!!! thank you Mayank. $\endgroup$ – Ilan Aizelman WS Aug 17 '16 at 12:58

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.


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*}$$


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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