1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Actually, you have $T(3) = 1$ so you can just use that. $\endgroup$ – Qudit Oct 11 '17 at 7:00
  • $\begingroup$ 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}$. $\endgroup$ – user316270 Oct 11 '17 at 7:08
0
$\begingroup$

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:

enter image description here

$\endgroup$

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.