Big O Substitution Proof

Document last modified:

Use the substitution method to show that T(n) ∈ O(n² lg n)

where T(n) =	1 when n = 1
	16T(n/4) + n² when n > 1

1) By definition of Big-O:

T(n) ≤ c * n² lg n

where O(g(n)) = {h(n): ∃ positive constants c, n₀ such that 0 ≤ h(n) ≤ cg(n), ∀ n ≥ n₀}

2) IH: T(n/4) ≤ c * (n/4)² lg n/4

3) Show: T(n) ≤ c * n² lg n n case defined by n/4 case

Figuring out constant c so the last two lines are correct.

Write those two lines (lines 5 and 6) down as follows, then do algebra to solve for the constant c:

By definition of Big-O, c is required > 0

4) Base case to find n₀

Verify: T_R(n) ≤ T_C(n)

T_R(n) = T(n) recurrence

T_C(n) = cn² lg n closed-end bounds solution for O

where T_R(n) =	1 when n = 1
	16T_R(n/4) + n² when n > 1

Try n₀ = 1

Try n₀ = 4

fails for n₀ = 1

succeeds when c ≥ 1 and n₀ = 4

5) Base case c ≥ 1

Induction c ≥ 1/2

Since T(n) ≤ c * n² lg n, ∀n ≥ n₀choose c ≥ 1 and n₀ = 4,

T(n) ∈ O(n² lg n)