the substitution method
Sometimes the cleanest way to confirm a running time is the most direct one: guess the answer, then prove your guess is right. It feels like cheating — you write down the conclusion first — but the proof is where the honesty lives, and a wrong guess simply fails to prove.
The substitution method has two steps. First, guess a closed-form bound, for example T(n) = O(n log n). Second, substitute that guess into the recurrence and prove it by induction: assume the bound holds for all sizes smaller than n (the inductive hypothesis), plug it in, and show it then holds for n. Concretely, to show T(n) = 2 T(n/2) + n is O(n log n), guess T(n) <= c n log n. Assume T(n/2) <= c (n/2) log(n/2). Then T(n) <= 2 c (n/2) log(n/2) + n = c n (log n - 1) + n = c n log n - c n + n, which is <= c n log n as long as c >= 1. The induction goes through, so the bound holds.
Two practical points keep it honest. You must choose the constant c (and the base-case range) so that the inequality closes for ALL n above some threshold, not just one convenient value. And the method only verifies a bound you already suspect — it does not discover the answer for you; for that you draw a recursion tree first. A famous trap is needing to subtract a lower-order term to make the algebra close: to prove O(n) for T(n) = 2 T(n/2) + 1, guessing T(n) <= c n fails, but the stronger guess T(n) <= c n - d succeeds — a strengthened hypothesis is often the fix.
Prove T(n) = T(n-1) + n is O(n^2). Guess T(n) <= c n^2. Then T(n) <= c (n-1)^2 + n = c n^2 - 2 c n + c + n = c n^2 - (2c - 1) n + c <= c n^2 whenever c >= 1 and n >= 1. The hypothesis is maintained, so T(n) = O(n^2).
Plug the guess in, then push the algebra until the same bound reappears on the right.
Sloppy use hides a fatal error: you must produce the SAME constant c on both sides, not just an O(...) at the end. Writing 'T(n) <= 2 c (n/2) + n = c n + n = O(n)' is wrong — the leftover +n means the c-bound did NOT close; you proved O(n) for one step but not the induction.