Hai messo 2 per sbaglio anche nel tuo terzo messaggio. Stai cercando di usare l'induzione, anche se manca il caso base.
Supponiamo che \(\displaystyle n \) sia
sufficientemente grande1 e che si abbia \(\displaystyle T(n/2) = \Theta(n\log n) \). Allora \begin{align}k_1n \log \frac{n}{2} + c_1\log n & \le T(n) \le k_2n \log \frac{n}{2} + c_2\log n \\
\min(k_1, c_1) \biggl(n\log n - n \log 2 + \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n - n \log 2 + \log n \biggr) \\ \min(k_1, c_1) \biggl(n\log n - n + \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n - n + \log n \biggr) \end{align}
Ora è evidente che per \(\displaystyle n \)
sufficientemente grossa \(\displaystyle 0 < \log n < n < \varepsilon n\log n \) per un qualche \(\displaystyle 0 < \varepsilon < 1 \). Pertanto si ha che
\begin{align} \min(k_1, c_1) \biggl(n \log n - n + \log n \biggr) & \le T(n) \le \max(k_2, c_2)\biggl(n \log n - n + \log n \biggr) \\ \min(k_1, c_1) \biggl(n \log n - \varepsilon n \log n \biggr) & \le T(n) \le \max(k_2, c_2) \biggl(n \log n + \varepsilon n\log n \biggr) \\ (1-\varepsilon)\min(k_1, c_1) n \log n & \le T(n) \le (1+\varepsilon)\max(k_2, c_2) n \log n \end{align}
Il caso base è un po' tedioso dato che si ha \(\displaystyle \Theta(\log n) \) invece che un più fattibile \(\displaystyle c\log n \).
[edit] Mi ero dimenticato della moltiplicazione per 2.