# Recurrence relation by substitution

I have an exercise where I need to prove by using the substitution method the following $$T(n) = 4T(n/3)+n = \Theta(n^{\log_3 4})$$ using as guess like the one below will fail, I cannot see why, though, even if I developed the substitution $$T(n) ≤ cn^{\log_3 4}$$ finally, they ask me to show how to substract off a lower-order term to make a substitution proof work. I was thiking about using something like $$T(n) ≤ cn^{\log_3 4}-dn$$ but again, I cannot see how to verify this recurrence.

What I did:

$$T(n) = 4T(n/3)+n$$ $$\qquad ≤ \frac{4c}{3}n^{\log_3 4} + n$$

and then from here, how to proceed and conclude that the first guess fails?

The complete exercise says:

Using the master method, you can show that the solution to the recurrence $T(n) = 4T(n/3)+n$ is $T(n)=\Theta(n^{log_3 4})$. Show that a substitution proof with the assumption $T(n) ≤ cn^{log_3 4}$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.

• Do you have any familiarity with solving such problems? Do you know what the terms general solution and specific solution means? – Calvin Lin Jan 4 '13 at 22:53
• Yeah, more or less. I was following Cormen's book of Algorithms and try to solve it using the examples, but I quite don't get it. – BRabbit27 Jan 4 '13 at 23:01
• This is a standard problem, with a standard approach. You should 'guess' that the substitution is $S(n) = T(n) +kn$, and then calculate that with $k=3$, we get $S(n) = 4S(n/3)$. This is where $\log_3 4$ comes from. – Calvin Lin Jan 4 '13 at 23:04
• Could you develop more your suggestion, please? – BRabbit27 Jan 4 '13 at 23:11
• 1) Solving T(n) = A T(n/B) is extremely easy and you should know how to do this. 2) If T(n) = A T (n/B) + f(n), then use a substitution, S(n) = T(n) - g(n), such that g(n) - Ag(n/B) = f(n), which makes S(n) = S(n/B). – Calvin Lin Jan 4 '13 at 23:46

It seems the cause of your trouble is simply that you made a mistake while computing $(n/3)^{\log_34}$, which is $n^{\log_34}/4$ and not $n^{\log_34}/3$.

(Note that $(n/3)^{\log_34}=n^{\log_34}/3^{\log_34}$ and that $3^{\log_34}=\exp(\ln3\cdot\log_34)$ with $\ln3\cdot\log_34=\ln3\cdot\ln4/\ln3=\ln4$ hence $3^{\log_34}=4$.)

Anyway, the hint you were given is to assume that $T(n)\leqslant An^{\log_34}+Bn$ $(*)$ and to check if $(*)$ is hereditary for some suitable $B$. Hence, assume $(*)$ holds for $n/3$, then $$T(n)=4T(n/3)+n\leqslant 4A(n/3)^{\log_34}+4B(n/3)+n=An^{\log_34}+(4B/3+1)n,$$ and one sees that $(*)$ holds for $n$ as soon as $4B/3+1\leqslant B$, for example for $B=-3$.

Now, choosing $A$ large enough such that $T(n)\leqslant An^{\log_34}-3n$ holds for $n$ small, one sees that $T(n)\leqslant An^{\log_34}-3n$ holds for every $n$.

Likewise, there exists $A'$ such that $T(n)\geqslant A'n^{\log_34}-3n$ holds for $n$ small, and this is enough to guarantee that $T(n)\geqslant A'n^{\log_34}-3n$ holds for every $n$. Thus, $T(n)=\Theta(n^{\log_34})$.

In hindsight, all this can be made easier using the change of variable $\bar T(n)=T(n)+3n$ since $\bar T(n)=4T(n/3)+n+3n=4\bar T(n/3)$, a recursion whose solution can be computed directly.

• Yes, you were right I had an error when substituting. – BRabbit27 Jan 4 '13 at 23:26
• How is it that one sees that (∗) holds for n as soon as 4B/3+1⩽B, for example for B=−3. ?? – BRabbit27 Jan 5 '13 at 0:18
• Because it suffices that $An^{\log_34}+(4B/3+1)n\leqslant An^{\log_34}+Bn$, and for that, since $n\geqslant1$, $4B/3+1\leqslant B$ is enough. – Did Jan 5 '13 at 18:02

Let $n = 3^{m+1}$. Then we have $$T \left(3^{m+1} \right) = 4T \left(3^{m} \right) + 3^{m+1}$$ Let $T\left(3^m\right) = g(m)$. We then get that $$g(m+1) = 4g(m) + 3^{m+1} = 4(4g(m-1) + 3^m) + 3^{m+1} = 4^2 g(m-1) + 4\cdot 3^m + 3^{m+1}\\ = 4^2 (4g(m-2) + 3^{m-1}) + 4\cdot 3^m + 3^{m+1} = 4^3 g(m-3) + 4^2 \cdot 3^{m-1} + 4 \cdot 3^m + 3^{m+1}$$ Let $\lfloor m \rfloor = M$ Hence, by induction we get that $$g(m+1) = 4^M g(m-M) + \sum_{k=0}^{M-1} 4^k \cdot 3^{m+1-k} = 4^M g(m-M) + 3^{m+1} \sum_{k=0}^{M-1} (4/3)^k\\ = 4^M g(m-M) + 3^{m+1} \dfrac{(4/3)^M-1}{4/3-1}= 4^M g(m-M) + 3^{m+2} ((4/3)^M-1)$$ Hence, we get that $$g(m+1) = 4^M g(m-M) + 3^{m+2-M} \cdot 4^M - 3^{m+2}$$ To get the order, we can take $m$ to be an integer. Hence, $m=M = \log_3(n)-1$ and we get that $$g(m+1) = 4^{\log_3(n)-1} g(0) + 3^{2} \cdot 4^{\log_3(n)-1} - 3^{\log_3(n)+1}$$ Note that $4^{\log_3(n)} = n^{\log_3(4)}$. Hence, we get that $$T(n) = \dfrac{g(0)}4 n^{\log_3(4)} + \dfrac94 \cdot n^{\log_3(4)} - 3n$$

This recurrence has the nice property that we can give an explicit value for all $n$, not just powers of three. Let $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k$$ be the representation of $n$ in base three. With $T(0) = 0$, we have by inspection $$T(n) = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j} = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } d_{k+j} 3^k .$$ For a lower bound, consider those $n$ that consist of a leading one digit followed by zeroes. This gives $$T(n) \ge \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 3^{\lfloor \log_3 n \rfloor - j} = 3^{\lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} \left(\frac{4}{3}\right)^j$$ which is $$3^{\lfloor \log_3 n \rfloor} \frac{(4/3)^{1+ \lfloor \log_3 n \rfloor}-1}{4/3-1} = 4^{1+ \lfloor \log_3 n \rfloor} - 3^{1+ \lfloor \log_3 n \rfloor}.$$ For an upper bound, consider those $n$ that consist entirely of digits with value two. $$T(n) \le 2 \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \sum_{k=0}^{\lfloor \log_3 n \rfloor - j } 3^k = 2 \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j \frac{3^{1+\lfloor \log_3 n \rfloor - j}-1}{3-1} < \sum_{j=0}^{\lfloor \log_3 n \rfloor} 4^j 3^{1+\lfloor \log_3 n \rfloor - j}$$ which is $$3^{1+ \lfloor \log_3 n \rfloor} \sum_{j=0}^{\lfloor \log_3 n \rfloor} \left(\frac{4}{3}\right)^j = 3^{1+\lfloor \log_3 n \rfloor} \frac{(4/3)^{1+ \lfloor \log_3 n \rfloor}-1}{4/3-1} = 3 \times 4^{1+ \lfloor \log_3 n \rfloor} - 3 \times 3^{1+ \lfloor \log_3 n \rfloor}$$ What we have shown here is that for all $n$, $$T(n) \in \Theta\left(4^{1+ \lfloor \log_3 n \rfloor} - 3^{1+ \lfloor \log_3 n \rfloor}\right) = \Theta\left(4^{1+ \lfloor \log_3 n \rfloor}\right) = \Theta\left(4^{\lfloor \log_3 n \rfloor}\right).$$ But $$4^{\lfloor \log_3 n \rfloor} \le 4^{\log_3 n} = 4^{\frac{\log_4 n}{\log_4 3}} = n^{\frac{1}{\log_4 3}} = n^{\log_3 4}$$ and similarly $$4^{\lfloor \log_3 n \rfloor} > 4^{\log_3 n -1} = \frac{1}{4} 4^{\frac{\log_4 n}{\log_4 3}} = \frac{1}{4}n^{\frac{1}{\log_4 3}} = \frac{1}{4}n^{\log_3 4}$$ so that finally $$T(n) \in \Theta\left(n^{\log_3 4}\right).$$