[CLRS] [4-6] Proof of the continuous master theorem

1. Introduction

- [4-5] 에선 마스터 정리에 대한 공식을 알아 봤다면, 이 공식이 어떻게 나왔는지 증명을 통해서 알아보자.

 

2. Proof

- 1) T(n)을 시그마를 이용하여 정리한다.

 

- 2) c < log_b(a) 일때 

 

 

- 3) c = log_b(a) 일 때,

 

- 4) c > log_b(a) 일 때,