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.

  • $\begingroup$ Do you have any familiarity with solving such problems? Do you know what the terms general solution and specific solution means? $\endgroup$ – Calvin Lin Jan 4 '13 at 22:53
  • $\begingroup$ 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. $\endgroup$ – BRabbit27 Jan 4 '13 at 23:01
  • $\begingroup$ 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. $\endgroup$ – Calvin Lin Jan 4 '13 at 23:04
  • $\begingroup$ Could you develop more your suggestion, please? $\endgroup$ – BRabbit27 Jan 4 '13 at 23:11
  • $\begingroup$ 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). $\endgroup$ – 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.

  • $\begingroup$ Yes, you were right I had an error when substituting. $\endgroup$ – BRabbit27 Jan 4 '13 at 23:26
  • $\begingroup$ How is it that one sees that (∗) holds for n as soon as 4B/3+1⩽B, for example for B=−3. ?? $\endgroup$ – BRabbit27 Jan 5 '13 at 0:18
  • $\begingroup$ 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. $\endgroup$ – 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).$$


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.