# Solve the recurrence relation $T(n)=4T(n/3) + n$, $T(3) = 1$, $n = 3^k$ then determine upper and lower bounds

I would like to solve the following recurrence relation. After which I must find it's upper and lower bounds.

$T(n)=4T(\frac{n}{3})+n, T(3)=1, n = 3^k$

I attempted to solve with substitution:

k = 1: $T(n)=4T(\frac{n}{3})+n$
k = 2: $T(n)=4^2T(\frac{n}{3^2})+\frac{4n}{3}+n$
k = 3: $T(n)=4^3T(\frac{n}{3^3})+\frac{4^2n}{3^2}+\frac{4n}{3}+n$

General: $T(n)=4^kT(\frac{n}{3^k})+\sum_{i=1}^k(\frac{4^{i-1}}{3^{i-1}})n=4^kT(\frac{3^k}{3^k})+...=4^kT(1)+...$

Q1: Here is where my first problem arrived; I was not given a relation for T(1) so I can not finish with substitution, right? Perhaps my professor made a typo and meant to put T(1) = 1?

Assuming that he didn't make a typo, I decided to try and solve the problem using Master Theorem:

Master Theorem: $T(n)=aT(\frac{n}{b})+n^d$ where $a,b > 0$ and $d\ge0$ then

$T(n)=\Theta(n^d)$ if $d>\log_b(a)$
$T(n)=\Theta(n^d\log(n))$ if $d=\log_b(a)$
$T(n)=\Theta(n^{\log_b(a)})$ if $d<\log_b(a)$

Using this method I get $T(n)=\Theta(n^{1.262})$

Q2: I read that $\Theta(g(n))$ is both the upper bound $O(g(n))$ and the lower bound $\Omega(g(n))$ so does that mean that the three answers to my question would be...

Solution to recurrence relation: $T(n)=\Theta(n^{1.262})$
Upper bound: $O(n^{1.262})$
Lower bound: $\Omega(n^{1.262})$

• Actually, you have $T(3) = 1$ so you can just use that. – Qudit Oct 11 '17 at 7:00
• The case in when $T(3) = 1$ has the overall term of $4^{k-1}T(\frac{n}{3^{k-1}})$. When this occurs, and after the substitution $T(3) = 1$, the term becomes $4^{k-1}$. – user316270 Oct 11 '17 at 7:08

Q1: Here is where my first problem arrived; I was not given a relation for T(1) so I can not finish with substitution, right? Perhaps my professor made a typo and meant to put T(1) = 1?

No, your professor was correct in providing $T(3) = 1$, given $n = 3^{k}$. As you may have noticed when using substitution method, there is generally a relationship in the power of the coefficient - in this case, $4$ - and the power of the denominator in $T()$. Realizing this, you can often quickly generalize and jump to the base condition. To explicitly illustrate:

\begin{align} T(n) &= 4^{1}T(\frac{n}{3^{1}}) + n \\ &= 4^{2}T(\frac{n}{3^{2}}) + 4n + n \\ &= 4^{3}T(\frac{n}{3^{3}}) + 4^{2}n + 4n + n \\ & = \ ... \end{align}

At this point, look to the value within $T()$ in order to determine the remaining number of additional substitutions need to take place. For this problem, the base case is $T(3) = 1$, and,

$$3 = \frac{n}{3^{k-1}}$$

therefore, we get

\begin{align} T(n) &= 4^{k-1}T(\frac{n}{3^{k-1}}) + 4^{k-2}n + ... + 4^{k - (k - 1)}n + n \\ & = 4^{k-1} + 4^{k-2}n + ... + 4^{k - (k - 1)}n + n \end{align}

Now, these terms need to be summed. Re-expressing $4 = 2^{2}$ and factoring out $n$,

\begin{align} T(n) & = 2^{2(k-1)} + 2^{2(k-2)}n + ... + 2^{2(k - [k - 1])}n + n \\ & = 2^{2(k-1)} + n(2^{2(k-2)} + ... + 2^{2(k - [k - 1])} + 1) \end{align}

Recognizing the parenthesized terms collectively represent a geometric series, we can easily sum the terms to get

\begin{align} T(n) &= 2^{2(k-1)} + n\sum_{i=1}^{k-2} \ (2^{2})^{i} \\ &= 2^{2(k-1)} + n(2^{2(k-2)+1} - 1)\end{align}

Lastly, back substitute $k$ to get

\begin{align} T(n) &= 4^{(log_{3}(n)-1)} + n(4^{(log_{3}(n)-2)+1} - 1) \\ &= 4^{log_{3}(n)-1}(n+1)-n \end{align}

Q2: I read that Θ(g(n)) is both the upper bound O(g(n)) and the lower bound Ω(g(n)) so does that mean that the three answers to my question would be...

Using case 1 of the Master Theorem as described by here, $T(n) \in \Theta(n^{1.262})$. Using theta notation alone will suffice for describing the bounds for this function, as it's implied in its definition. Consider the following graph: