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)?
 A: 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$
A: Suppose $T(n) = 2T(\lfloor \frac{n}{2} \rfloor + 17) + n$ for all $n$ and that $T(n) = O(n \log n)$ for $n$ less than some bound $k$. Take $n = k > \lfloor \frac{n}{2} \rfloor + 17$, then we use the recursion: 
$T(n) = 2T(\lfloor \frac{n}{2} \rfloor + 17) + n$
Since $T(n) = O(n \log n)$ for values smaller than $k$, there exists a constant $c$ such that $T(n) \leq c n \log n$. Therefore, $T(\lfloor \frac{n}{2} \rfloor + 17) \leq c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17)$.
Therefore, $T(n) \leq 2c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$.
Now, with a little algebra we want to show that for the same constant $c$, this works out to $T(n) \leq c n \log n$.
A: To show that T(n)=O(n log n) first assume that the result holds for all m

So assume that for all m< n, T(n)≤ c n log n
T(n)=2T(⌊n/2⌋+17)+n
    = 2c(⌊n/2⌋+17)log(⌊n/2⌋+17)+n

    = 2c(⌊n/2⌋+17)log(⌊n/2⌋+17)+n

now expand the above equation.
so T(n) = 2c⌊n/2⌋log(⌊n/2⌋+17) + 34clog(⌊n/2⌋+17) + n
but we know that, 2⌊n/2⌋ ≤ n, Therefore,
T(n) ≤ c nlog(2(⌊n/2⌋+17)/2) + 34c log(2(⌊n/2⌋+17)/2) + n 
(We have multiplied and divided each term inside the log functions)
so, T(n) ≤ c nlog((n+34)/2) + 34c log((n+34)/2) + n 
T(n) ≤ c nlog((n+34)/2) + 34c log((n+34)/2) + n 
T(n) ≤ c nlog(n+34) + 34c log(n+34) + n + ( cn log(1/2)+ 34c log(1/2) )
T(n) ≤ c nlog(n+34) + 34c log(n+34) + n - ( cn + 34c )
by taking out n inside the statements in log functions,
T(n) ≤ c nlog(n(1+34/n)) + 34c log(n(1+34/n)) + n - ( cn + 34c )
T(n) ≤ c nlog(n) + c (n+34)log(1+34/n) + 34c log(n)  + n -  c(n + 34)
when n is very large (n goes to infinity 34/n goes to zero and (n+34) goes to n). Therefore,
T(n) ≤ c nlog(n) + c nlog(1)  + n - cn
T(n) ≤ c nlog(n) - n (c-1)
So T(n) ≤ cn log(n) whenever c is greater than or equal to 1
Therefore the T(n)= O(nlogn)
