마스터 정리

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

이런 형태의 점화식을 푼다.
a(>=1),b(>1) 상수
f(n)은 점근적으로 양인 함수.

T(n)의 점근적 한계는 다음과 같다. (암기가 필요하다)
1. 상수 ε(>0)에 대해 f(n)=O(n^(logba-ε))이면 T(n)=θ(n^(logba))이다.

2. f(n)=θ(n^(logba))이면, T(n)=θ(n^(logba)lgn)이다.

3. 상수 ε(>0)에 대해 f(n)= Ω(n^(logba+ε)이고 상수 c(<1)와 충분히 큰 모든 n에 대해 af(n/b)<=cf(n)이면, T(n)=θ(f(n))이다.

첫 번째 경우 f(n)이 n^(logba)보다 작아야 할 뿐 아니라 다항식적으로 작아야 한다.
세 번째 경우 f(n)이 n^(logba)보다 커야할 뿐 아니라 다항식적으로 커야 하고 af(n/b) <= cf(n) 이라는 정규조건을 만족시켜야 한다.