<s>[INST] Showing that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$ How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$? What is the resulting equation I get after the substitution? 
$$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$
or
$$ T(n) = 2c \cdot  \left(\frac n2 + 17\right) \cdot \log \left(\frac n2 + 17\right) + n $$
To me the first equation looks the correct, but the professor came to the second equation after the substitution. Which one of the two is correct, and how do I proceed in solving it (because that $17$ can be quite tricky)?
 [/INST] After the inductive step we have:
$T(n) \le 2c(\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$
Note that $2 \lfloor \frac{n}{2} \rfloor \le n$ and we can get
$T(n) \le c(n + 34) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$
Expand to 
$ T(n) \le cn\log (\lfloor \frac{n}{2} \rfloor + 17) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$
Now add and subtract $cn \log n$
$ T(n) \le cn \log n - cn \log n + cn\log (\lfloor \frac{n}{2} \rfloor + 17) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$
$ T(n) \le cn \log n + cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$
Now show the expression $cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$ is negative for $n$ large enough and a correct choice of $c$ so that we can replace with 
$ T(n) \le cn \log n$
Showing negativity
$cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n \le 0$ 
For large $n$, the first term $cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n})$ will be close to $cn\log(\frac{1}{2})$  which is negative. The other two terms are $O(n)$ so we hope we can choose a $c$ so that the first term can overtake the other two.
$cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n \lt $  
$cn\log (\frac{ \frac{n}{2} + 17}{n}) + 34c\log ( \frac{n}{2} + 17) + n = $
$cn\log (\frac{1}{2} + \frac{17}{n}) + 34c\log ( n (\frac{1}{2} + \frac{17}{n})) + n = $
$cn\log (\frac{1}{2} + \frac{17}{n}) + 34c\log n + 34c\log(\frac{1}{2} + \frac{17}{n}) + n = $
$cn\log (\frac{1}{2} ( 1 + \frac{34}{n})) + 34c\log n + 34c\log(\frac{1}{2}(1  + \frac{34}{n})) + n = $
$cn\log \frac{1}{2} + cn \log( 1 + \frac{34}{n}) + 34c\log n + 34c\log\frac{1}{2}
 + 34c\log(1  + \frac{34}{n}) + n \lt$
... now choosing any $ 0 < \epsilon \ll 1$  and $n$ large enough ...
$cn\log \frac{1}{2} + cn \epsilon + 34c\log n + 34c\log\frac{1}{2}
 + 34c\epsilon + n =$
$c(n\log \frac{1}{2} + n \epsilon + 34\log n + 34\epsilon) + 34c\log\frac{1}{2}
  + n \lt$
$c(n\log \frac{1}{2} + n \epsilon + 34\log n + 34\epsilon) + n $
Now note that $n\log \frac{1}{2} + n \epsilon + 34\log n + 34 \epsilon= n(\log \frac{1}{2} + \epsilon ) + 34 \log n + 34\epsilon \equiv g(n)$ is negative for large enough $n$ since we have a negative linear function competing with a postive $\log$ function.
It only remains to show we can choose $c$ such that for large enough $n$,
$cg(n) + n \lt 0$
But we can do so, since $|g(n)| \in O(n)$, a $c$ exists such that it can outcompete the postive term  $ n$
</s>