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?