###The Master Theorem:

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

  1. If where , then .
  2. If where , then .
  3. If where , then .

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


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.