Studying Algorithms -- Solving Recurrence

Master method to solve recurrence with some particular form like:

T(n) = a * T(n/b) + f(n)

conditions: a>=1, b>1, f(n): asymptotic positive,

means: problem 'T()' of size 'n' can be separated into 'a' parts of problem 'T()' of size 'n/b', and then merge them for cost of 'f(n)'.

There's three common cases, by f(n) vs power(n, log(b, a)):

1) f(n) = Θ(power(n, (log(b,a) - ∈)) (for ∈> 0)
means f(n) is polynomially smaller than power(n, log(b,a))
SOLUTION: T(n) = Θ(power(n, log(b, a))

Example: T(n) = 4T(n/2) + n
==> f(n) = n; a = 4; b = 2; power(n, log(b,a)) = power(n, 2)
==> f(n) = Θ(power(n, 2-∈)) for ∈= 1
==> T(n) = Θ(power(n, 2))

2) f(n) = Θ(power(n, log(b,a)) * power(lg(n), k)) (for k >= 0)means f(n) grows at similar speeds with power(n, log(b,a))
SOLUTION: T(n) = Θ(power(n, log(b,a)) * power(lg(n), k+1))

Example: T(n) = 4T(n/2) + power(n, 2)
==> f(n) = power(n, 2); a = 4; b = 2; power(n, log(b,a)) = power(n, 2)
==> f(n) = Θ(power(n, 2)) for k = 0
==> T(n) = Θ(power(n, 2) * lg(n))

3) f(n) = Q(power(n, (log(b,a) + ∈)) (for ∈> 0)
and regularity condition: a*f(n/b) ≤ c*f(n) for constant c less than 1 means f(n) grows polynomially faster than power(n, log(b, a))

Example: T(n) = 4T(n/2) + power(n, 3)
==> f(n) = power(n, 3); a = 4; b = 2; power(n, log(b,a)) = power(n, 2)
==> f(n) = power(n, 2+∈) for ∈= 1 with regularity condition:
==> a * f(n/b) ≤ c * f(n) for (c less than 1)
==> 4 * power((n/2), 3) ≤ c * power(n, 3)
==> if c in [1/2, 1]
==> T(n) = Θ(power(n, 3))