Show that the solution to \(T(n) = 2T(\lfloor n/2 \rfloor + 17) +n\) is \(O(n \lg n)\).
Let us assume \(T(n) \le c n \lg n\) for all \(n \ge n_0\), where \(c\) and \(n_0\) are positive constants.
\[\begin {aligned} T(n) & \le 2c (\lfloor n/2 \rfloor + 17) \lg (\lfloor n/2 \rfloor + 17) + n \\ & \le 2c (n/2 + 17) \lg (n/2 + 17) + n \\ & = 2c ((n + 34) / 2) \lg ((n + 34) / 2) + n \\ & = c (n + 34) \lg (n + 34) - c (n + 34) \lg 2 + n \\ & = c (n + 34) \lg (n + 34) - ((c - 1)n + 34c) \\ \end {aligned}\]As you can see, we could not prove our initial hypothesis.
We’ll try again after subtracting a lower-order (in this case, constant) term from our initial assumption. And as we have an extra 34 in our final step, we’ll subtract the same from our initial guess.
Let’s assume, \(T(n) \le c (n - 34) \lg (n - 34)\) for all \(n \ge n_0\), where \(c\) and \(n_0\) are positive constants.
\[\begin {aligned} T(n) & \le 2c (\lfloor n/2 \rfloor + 17 - 34) \lg (\lfloor n/2 \rfloor + 17 - 34) + n \\ & \le 2c (n/2 - 17) \lg (n/2 - 17) + n \\ & = 2c ((n - 34) / 2) \lg ((n - 34) / 2) + n \\ & = c (n - 34) \lg (n - 34) - c (n - 34) \lg 2 + n \\ & = c (n - 34) \lg (n - 34) - ((c - 1)n - 34c) \\ & \le c (n - 34) \lg (n - 34) \end {aligned}\]The last step holds as long as \(((c - 1)n - 34c) \ge 0\)
We can pick \(c \ge 1\) and \(n \ge 43c / (c - 1)\).