Show that the solution to \(T(n) = 2T(\lfloor n/2 \rfloor + 17) + n\) is \(O(n \lg n)\).

We guess that \(T(n) \leq c(n-b) \lg(n-b)\). Substituting this into the recurrence yields

\[\begin{split} T(n) & \leq 2c(\lfloor n/2 \rfloor - b + 17) \lg (\lfloor n/2 \rfloor - b + 17) + n \\ & \leq 2c(n/2 + 1 + 17 -b) \lg (n/2 + 1 + 17 - b) + n \\ & = c(n + 36 - 2b) \lg (n + 36 -2b) - c(n + 36 -2b) + n \ \ \ ( b \geq 36 ) \\ & = c(n - b) \lg (n - b) - c(n - b) + n \\ & = c(n - b) \lg (n - b) - cn + bc + n \\ & \leq c(n-b) \lg (n-b) \\ \end{split}\]

Where the last step \(c(n - b) \lg (n - b) - cn + bc + n \leq c(n-b) \lg (n-b)\) holds for any \(c \geq 2\).