T(n) = 2 · T(n/2) + n
n^(log_b a)
n^(log_2(2)) = n
Compare
f(n) = n vs n
Case 2
f(n) = n = Θ(n) = Θ(n^(log_b a))
f grows at THE SAME RATE as n^(log_b a) = n.
Case 2 applies.
T(n) = Θ(n log n)
Case 1: f = O(n^(log_b a−ε)) → T = Θ(n^(log_b a)) Case 2: f = Θ(n^(log_b a)) → T = Θ(n^(log_b a)·log n) Case 3: f = Ω(n^(log_b a+ε)) + regularity → T = Θ(f(n))