Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$.
Here's what I tried –
Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot \lg(\lfloor n/2 \rfloor + 17)$ for some constant $c$ and for some $n \ge n_0$
Inductive step:
$$
\begin{split} T(n) &\le 2c(\lfloor n/2\rfloor + 17) \lg(\lfloor n/2\rfloor + 17) + n
\\ & \le 2 c (n/2 + 17)\lg(n/2 + 17) + n
\\ & \le c (n + 34) \lg((n+34)/2) + n
\\ & = c(n+34)\lg(n+34) – cn – 34c + n
\\ & \le c (n + 34)\lg(n + 34) \quad \text{(for $c \ge 1$)} \end{split}$$
So I am stuck here… how do I 'remove' the $34$s from this inequality? (This is exercise 4.3-6 of CLRS)
(Thanks @user137481)
The above reduces to
$T(n) <= cn.lg(n) + cn$ which is not quite $O(nlg(n))$. As described in CLRS, in such situations even if the inductive hypothesis is correct, we may not be able to arrive at the exact form. In this case we are offset by a lower order term $cn$ needs to be removed. So the new guess is $T(n) <= cnlg(n) – dn$, (this is still,of course, $O(nlg(n)$). Now,
$T(n) \le 2.c.(\lfloor n/2\rfloor + 17).lg(\lfloor n/2\rfloor + 17) – 2dn + n$
$ \le 2.c.(n/2 + 17).lg(n/2 + 17) -2dn + n$
$= c(n+34).lg(n+34) – c(n+34) – 2dn + n$
$\le 2cn.lg(2n)-2cn-2dn+n\;$ (for $n>=34$)
$=cn.lg(n) – cn + dn +n\;$ (absorbing 2 into c)
$\le cn.lg(n)\;$ (for all $c – d \ge 1$)
Therefore, $T(n) = O(n.lg(n))$
(This is what I have done, if there is any mistake, please correct me, if not, I will rewrite this as an answer and accept it).
Best Answer
As noted in the comments, when computing the "big-O" asymptotic form of a function, you can impose any lower bounds on the input $n$ that you like (for example, require $n > 34$). And you know that you can multiply an expression by a constant factor without changing its "big-O" form.
Once you have found that $T(n) \le c\cdot(n+34)\cdot\lg(n+34),$ then you can conclude, for $n > 34,$
$$\begin{eqnarray} T(n) &\le& c\cdot(n+34)\cdot\lg(n+34) \\ &\le& c\cdot(2n)\cdot\lg(2n) \\ &\le& 2cn\cdot(1 + \lg n) \\ &\le& 2cn\cdot(2 \lg n) = 4c\cdot(n \lg n) = O(n \lg n). \\ \end{eqnarray}$$
You had already found everything up to the last line of that sequence of inequalities. The key is that you can continue to introduce additional multiplicative constants as long as it helps simplify your function.