Solving recurrences using substitution method

ignougroup
Problem Detail: 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 cnlg 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?

Asked By : Harrison Nguyen

Answered By : zrbecker

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 $$logleft( frac{n + 34}{2} right) le logleft( 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 $$logleft( frac{n + 34}{2} right) le logleft( frac{n + n/2}{2} right) = logleft( frac{2n + n}{4} right) = logleft(frac{3n}{4}right) = log(n) + log(3/4).$$
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14347