Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$.
I am supposed to use the substitution method..
That's what I have tried:
Let $T(n)=O(n \lg n)$
In order the recursive relation to be well-defined,I thought to use the inequality $\lfloor x \rfloor \geq x-1$ and I found:
$$ \lfloor \frac{n}{2} \rfloor+17 \leq n \Rightarrow n \geq \lfloor \frac{n}{2} \rfloor +17> \frac{n}{2}-1+17 \Rightarrow n>\frac{n}{2}+16 \Rightarrow n\geq 33$$
$$\text{ So, } n_0=33$$
I have tried to show it,supposing $T(n) \leq cn\lg n$,then I supposed that the relation also stands for $\lfloor \frac{n}{2} \rfloor +17: T(\frac{n}{2} \rfloor +17) \leq c( \lfloor \frac{n}{2} \rfloor +17) \lg (\lfloor \frac{n}{2} \rfloor+17)$
So:
$$T(n) \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg (\lfloor \frac{n}{2} \rfloor+17)+n \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg n+n \leq 2c(\frac{n}{2}+17) \lg n+n \leq c(n+34) \lg n +n$$
But,like that,we cannot show what we want to..
Then,I tried it like that:
$$$$
As $T(n)=O(n \lg n)$,we suppose that $\exists c,b>0 \text{ such that } \forall n \geq 33 : T(n) \leq c(n-b) \lg n$
We suppose that the relation stands also for $\lfloor \frac{n}{2} \rfloor+17$,then: $T(\lfloor{\frac{n}{2}} \rfloor+17) \leq c(\lfloor \frac{n}{2} \rfloor +17-b) \lg (\lfloor \frac{n}{2} \rfloor+17)$
$$T(n)\leq 2c(\lfloor \frac{n}{2} \rfloor+17-b) \lg ( \lfloor \frac{n}{2} \rfloor +17)+n \leq 2c (\frac{n}{2}+17-b) \lg n+n = c(n-b+(34-b)) \lg n +n \leq c(n-b) \lg n +n,\text{ if } 34 \leq b$$
We also know that it must be $ T(n)\geq 0 \Rightarrow n \geq b \Rightarrow b\leq n, \forall n \geq n_0 \Rightarrow b\leq n_0 \Rightarrow b \leq 33$
So,we have a contradiction..Also,even if it was not a contadiction,we couldn't do it in this way,because: $c(n-b) \lg n +n \geq c(n-b) \lg n$
How can we show it then?