###The Master Theorem:

Let be a function defined on nonegative integers and taking positive value, if it satisfies for , then

- If where , then .
- If where , then .
- If where , then .

**主定理(The Master Theorem)**提供了用渐进符号表示许多由分治法得到的递推关系式的方法，因而在算法分析中广泛地使用。

###Proof:

Let’s first set a weaker problem and think about the recursion tree for this recurrence. There will be levels. At each level, the number of subproblems will be multiplied by , and so the number of subproblems at level will be . Each subproblem at level is a problem of size , which needs another work. So the total number of units of work on level is

In general, we have the total work done is

In **Case 1**, we see , so we have
when

So **Case 1** holds.

In **Case 3**, we have , then
converge to some constance. So we have

So **Case 3** holds.

Finally let’s take a look at a little more strict **Case 2**. Just take and change the work done on level to

Then in general the total work needs done is

So **Case 2** holds.