DinS          Written on 2017/12/17

1. What’s Master Method?

It’s an analysis tool for recursive algorithm. As long as all subproblems have equal size, you can just plug in numbers to get the running time. A very convenient and powerful tool.

2. Formal statement

Define T(n) as the maximum number of operations. We can format recursive algorithm as follows:

Where     a = number of recursive calls (>=1)

b = input size shrinking factor (>1)

d = exponent in summing time of combine step (>=0)

a, b and d are independent of n.

After that, the following formula holds true:

This may seem mysterious at first. Let’s try an example here.

We know MergeSort can be written as this : T(n) = 2T(n/2) + O(n), which means that, if we extract the numbers, a=2, b=2, d=1. This belongs to the first case, since 2 = 2¹. As a result, we can plug in the numbers to get the running time for MergeSort. That’s exactly O(nlogn).

3. Proof

What’s going on? Let’s try to prove this Master Method.

If you understand what we did in the MergeSort analysis, this is just a generalization. “a” equals number of recursive calls. In other words “a” determines how fast we split the original problems into subproblems. If a=2, each call yields 2 more calls, then at level j we’ll have 2^j subproblems. To generalize a bit, at level j we’ll have a^j subproblems.

The same goes for “b”. “b” actually means how fast the original problem size shrinks. If b=2, each call will shrink the problem size to half, then at level j the subproblem size will be . To generalize a bit, at level j the subproblemsize will be .

In summary, the total work at level j will be  

Notice the “c” here. We’re taking the O() off in the general case, so there should be some constant.

Now that we’ve got the work on each level, the total operations for the whole algorithm should be the sum of work in each level. Thus we get this.

This should be clear. For a problem of size n, we have  log_bn level. This explains the notations of that sum.

What should we do next? Let’s interpret the * a bit. “a” can be understood as the rate of subproblem proliferation, while b^d can be understood as the rate of work shrinkage. It’s like a tug of war. If subproblems grow faster than work shrinkage, we need to do more work. If work shrinks faster than subproblem growth, we need to do less work. If they’re the same, work remains unchanged.

Now let’s try out our interpretation. First, case I.  . That is to say, we have same amount of work on each level. If that’s the case, * becomes something like this.

Second, case II. If a < b^d, that means less work to do on each level. In other words, most work at the root. We let  , and * becomes something like this.

And there’s a formula for this sum. (See the Series article here)

If r<1, then the above <= , which is a constant.

If r>1, then above <= 2r^k, a constant * biggest number.

For case II, we know r<1. Thus * can be written as this.

T(n) <= c * n^d * (a constant) = O(n^d)

Third, case III. Using the conclusion for case II, * can be written as this. (notice r > 1)