Substitution Method: Use the substitution method to show that T(n) is O(n log (n)): T(n) = 2T(n/2) + n. Solution: Recursion tree Method: Solve T(n) = T(n/4) + T(1/2) + n2: n2 n2 (n/4) (n/2) 5 16 25 256 (n/16)2 (n/8)2 (n/8)2 (n/4) n2 (1) Total = 1+(1+2+(3+() +... = O(n^) geometric series