# Solving recurrences using substitution method

I already have a solution for this problem but it's just not making sense to me.

Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4):

Show $T(n) = 2T(\lfloor n/2 \rfloor +17)+n$ is $O(n \log n)$

This is what I have so far:

So Assume $T(k) \leq cn\lg n$, for $k<n$.

\qquad \begin{align*} T(n) &= 2T(\lfloor n/2 \rfloor +17)+n \\ &\leq 2c(\lfloor n/2 \rfloor +17)\lg(\lfloor n/2 \rfloor + 17) +n \\ &\leq 2c(n/2 + 17) \lg (n/2 + 17) + n \\ &= c(n + 34) \lg((n+34)/2)+ n \end{align*}

And this is where I stop understanding what is going on. Looking at the solution to this problem tells me:

Note that $(n + 34)/2 \leq (3n)/4$ for $n \geq 68$ so that $\lg((n + 34)/2) \leq \lg((3n)/4) = \lg(n) + \lg(3/4)$ for $n \geq 68$.

But it fails to tell me why/how we know that $(n+34)/2 \leq 3n/4$ for $n \geq 68$. Where did this number come from and how would I arrive at this if I did not know the solution beforehand?

• You are aware that you are doing an induction proof here, however crippled you have written it down? I have no idea where the term "substitution method" originates; I prefer guess & prove. As for the constants, these are most likely derived by trial & error. – Raphael Sep 16 '13 at 8:52
• Yes, I know that it is induction. Computer scientists are taught of three ways to solve these recurrences: the "substitution" method, binary tree method, and master theorem. I'm not sure why CLRS chose "substitution" over induction, but there ya go. – Harrison Nguyen Sep 16 '13 at 13:21
• Meant to say recursion tree method, it is not always binary. – Harrison Nguyen Sep 16 '13 at 13:57
• Actually, there are more; see my link. Even that list is not complete! – Raphael Sep 16 '13 at 14:38

The complexity in your proof is that you have addition in you logarithm, and you need that complexity to go away. So lets get rid of that 34, by just making $n \ge 34$, so now

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n}{2} \right) = \log(n).$$

I am not sure why the book chose 68, but really its the same argument. If $n \ge 68$, then $n/2 \ge 34$. Thus

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n/2}{2} \right) = \log\left( \frac{2n + n}{4} \right) = \log\left(\frac{3n}{4}\right) = \log(n) + \log(3/4).$$

• Awesome. I was able to finish my proof using this. Thanks a lot. – Harrison Nguyen Sep 16 '13 at 13:28

Let $n>34$ be an integer. We consider the sequence $u_0=n,u_{k+1}=floor(u_k/2)+17$. There is $p$ s.t. $u_p=34$ and we stop the process. Thus, if we know $T(34)$, then we use a back-tracking to obtain $T(n)$. The number of step is in $O(log(n))$. Inded the value $\delta=17$ is not important. In this case $\log_2(n)<p<\log_2(n)+1$. If $\delta=1000$, then let $q$ s.t. $u_q=2000$. Again $\log_2(n)<q<\log_2(n)+1$.

EDIT: Now the back-tracking: $T(u_{k-1})=2T(u_k)+u_{k-1}$. $T(n)=T(u_0)$ is in the form $a_nT(34)+b_n$ with $a_n=O(n)$. Let $v_p=0, v_{k-1}=2v_k+u_{k-1}$ ; then $b_n=v_0$. It remains to show that $b_n=O(n\log(n))$.

EDIT: At each step, $u_{k-1}\approx 2u_k$. Then one has approximately $v_p=0,v_{p-1}=2.0+2=2^1.1,v_{p-2}=2.2+4=2^2.2,v_{p-3}=2.8+8=2^3.3,v_{p-4}=2.24+16=2^4.4,v_{p-5}=2.64+32=2^5.5$ and, in general $v_{p-k}=2^k.k$. Finally $b_n\approx 2^p.p\approx n\log_2(n)$. In fact, we can prove $T(n)=\Theta(nlog(n))$.

EDIT: Hi Harrison, your (or that of your book !) reasoning by recurrence does not work because you obtain only $T(n)\leq cn\log(n)+n+o(n)$ instead of $T(n)\leq c(n+1)\log(n+1)=cn\log(n)+c\log(n)+o(\log(n))$.