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})$
Best Answer
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}
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: