Solving recurrences using substitution method

Question

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?

Answer 1

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

Answer 2

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