Master theorem (마스터 이론)

Divide and conquer algorithm에서 time complexity를 구할 수 있는 공식

-> 두 식 모두 표현 가능함.

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems

-> b로 나누어 a개로 풀음, f(n)은 sub에서 합치는 시간.

-> 합치는 시간에 따라 3가지 케이스로 나뉘어 time complexity 추정 가능함.

예시)

http://en.wikipedia.org/wiki/Master_theorem