$T(n)=2T(n/2)+n$ — Substitution Method, Upper Bound $O(n \log n)$

Guess: $T(n) \le c\, n \log n$ for some $c>0$, $n\ge n_0$ (with $T(1)=\Theta(1)$).

Inductive Hypothesis: Assume for $n/2$: $T(n/2) \le c (n/2) \log(n/2)$.

Inductive Step:
$$\begin{aligned} T(n) &= 2T(n/2)+n \\ &\le 2\left[ c\frac{n}{2}\log\frac{n}{2}\right]+n \\ &= c n (\log n - \log 2)+n \\ &= c n \log n - c n \log 2 + n \end{aligned}$$
With $\log$ base 2, $\log 2=1$:
$$T(n) \le c n \log n -c n + n = c n \log n -(c-1)n$$
Choose $c \ge 1$ → $-(c-1)n \le 0$ → $T(n) \le c n \log n$.

Base case: Need $T(1) \le c\cdot1\cdot\log1 =0$ fails for log base2. Use $T(2)$ or define $T(1)=1$, choose $n_0=2$, pick $c$ large enough: $c\cdot2\log2 \ge T(2)=2T(1)+2=4$ → $c\ge2$ works. More formally prove for $n\ge2$, or use $n\log n$ with $T(1)=\Theta(1)$ and show $T(n)\le c n\log n +b$ variant.

Hence $T(n)=O(n\log n)$.

Tight bound: Similarly show $T(n) \ge c' n\log n$ → $\Omega(n\log n)$ → $\Theta(n\log n)$.
By Master Theorem case 2 ($a=2$, $b=2$, $n^{\log_b a}=n^1$, $f(n)=n=\Theta(n^{\log_b a})$) → $T(n)=\Theta(n\log n)$.

Application: This is the Merge Sort recurrence.