$T(n)=aT(n/b) + f(n)$

여기에서 "$n/b$"는 $\lceil{n/b}\rceil$ 혹은 $\lfloor{n/b}\rfloor$를 의미함.
$(a\geq1, b>1, and\ f(n) > 0)$

Case 1

$f(n)=O(n^{log_b a-\epsilon})$ for some constant $\epsilon>0$

f(n) is pollynomially smaller than $n^{log_b a}$
Soluion: $T(n)=\Theta(n^{log_b a})$
Intuitively: Cost is dominated by leaves.

Case 2

$f(n)=\Theta(n^{log_b a\ lg^{k}n}), where\ k\geq0$

$f(n)$ is within a polylog factor of $n^{log_b a}$, but not smaller.
Solution: $T(n)=\Theta(n^{log_b a}lg^{k+1}n)$
Intuitively: Cost is $n^{log_b a}lg^k n$ at each level, and there are $\Theta(lgn)$ levels.

Case 3

$f(n) = \Theta(n^{log_b a+\epsilon})$ for some constant $\epsilon > 0$ and $f(n)$ satisfies the regularity condition $af(n/b)\leq cf(n)$ for some constant $c<1$ and all sufficiently large n.

f(n) is polynomially greater than $n^{log_b a}$
Solution: $T(n) = \Theta(f(n))$
Intuitively: Cost is dominated by root.

Example

• $T(n)=9T(n/3)+n$
  - $f(n)=n$
  - $n^{log_3 9}=n^2 \rightarrow Case\ 1\rightarrow T(n)=\Theta(n^2)$
• $T(n)=T(2n/3)+1$
  - $f(n)=1$
  - $n^{log_{3/2}1}=n^0=1 \rightarrow Case\ 2\rightarrow T(n)=\Theta(logn)$
• $T(n)=2T(n/2)+\Theta(n)$
  - $f(n)=\Theta(n)$
  - $n^{log_2 2}=n^1 \rightarrow Case\ 2\rightarrow T(n)=\Theta(nlogn)$
• $T(n)=5T(n/2)+\Theta(n^3)$
  - $n^{log_2 5}$ vs. $n^3$
  - $af(n/b)=5(n/2)^3 = 5n^3/8 \leq cn^3 for\ c=5/8 < 1$
  - $Case\ 3 \rightarrow T(n)=\Theta(n^3)$