Master Theore

Master Theorem을 이용하면 재귀적인 구조를 갖는 알고리즘의 시간복잡도를 간단하게 계산할 수 있다.

 

알고리즘이 시간복잡도  $T(n) = aT(\frac{n}{b}) + O(n^k)$  으로 표현될때,  $T(n)$  은 다음과 같이 계산할 수 있다.

 

$$
\begin{align}
&1. \; a>b^k \quad \Rightarrow \quad T(n) = O(n^{log_{b}{a}})\\
&2. \; a=b^k \quad \Rightarrow \quad T(n) = O(n^k log n)\\
&3. \; a<b^k \quad \Rightarrow \quad T(n) = O(n^k)
\end{align}
$$