algorithm) Master theorem

일반적으로 시간복잡도를 Asymtotic notation으로 나타낼 때는 Worst case인 O(Big-O) 표기법을 사용한다.

만약 시간복잡도 함수가 한 다항식으로 나타난다면, 이 중 가장 높은 차수의 항으로 표기한다.

재귀함수의 경우 다음과 같이 시간복잡도가 정의될 수 있다.
아래와 같은 형태는 최고차항을 직관적으로 파악하기가 어렵기 때문에 마스터 정리를 적용하여 쉽게 수행시간을 파악할 수 있다.

이를 기반으로 정의된 마스터 정리는 다음과 같다

아래는 증명과정이며, 주석은 내가 임의로 이해한 것을 적은 것이다. 때문에 정확하지 않을 수 있다.