Big O Substitution Proof
Document last modified: 

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

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

1) By definition of Big-O:

T(n) ≤ c * n2 lg n

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

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

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