재귀식을 통해 표현되는 알고리즘들의 시간 복잡도를 구할 때 유용하게 사용되는 방법 중 하나가 바로 Master Theorem이다. 이 방법을 사용하면, 굳이 문제를 나눠보지 않아도 시간 복잡도를 바로 구할 수 있다. ## Master Theorem 1. $T(n) = aT(\frac{n}{c}) + bn, \text{ for } n>1, T(1) = 1$ 1. $T(n) = O(n) \text{ if }a<c$ 2. $T(n) = O(n\log n) \text{ if }a=c$ 3. $T(n) = O(n^{log_ca}) \text{ if }a>c$ 2. $T(n) = aT(\frac{n}{b}) + O(n^d) \text{ for } a\ge 1, b>1, d\ge 0$ 1. $T(n) = O(n^{d}\log n) \text{ if } a=b^d$ 2. $T(n) = O(n^{d}) \text{ if } a<b^d$ 3. $T(n) = O(n^{\log_ba}) \text{ if } a=b^d$