Why does the Master Theorem Work?
The master theorem is a well-known method for evaluating the computational complexities of divide-and-conquer algorithms but why does it work? It is easy to follow along when looking a the tables. But how are the tables derived? Why do the relationships in the table hold true?
Before delving into the previous questions, a quick recap of the master theorem. The master theorem was first introduced in a paper by Bentley et al [1] (an updated version by Drmota and Szpankowski [2] also exists) and popularized by Cormen’s textbook Introduction to Algorithms (in which it also got its name as the master theorem). This paper demonstrates how to solve recurrence relations which are basically the same thing in practice as recursion. The basic premise behind the theorem is that recurrence relations have a certain pattern, which when identified, make it easier to determine their time complexity. Usually tables are used to quickly determine the complexity for a given recurrence relation. These tables are shown below.
The above relationships only hold for specific recurrence relations (as shown on the tables) with specific properties (a needs to be a positive constant, f(n) needs to be a polynomial, and T(n) needs to be monotone i.e. it does not change the general direction when graphed). There exists a more general approach called the Akkra-Bazzi method which allows us to analyze recurrence relations that don’t fit the requirements from the masster method but we will not use that now. Instead we will use another approach, analyzing the recursion tree of the relation. All recurrence relations can be turned into recursive programs and all recursive programs can be represented by recursion trees. We can use such trees to determine the total work done by the relation/program based on the relationships between the nodes. Let’s explore this further.
Starting with the recurrence relation from the first table, it can be represented visually using a tree as shown below.
The root node contains the original work done, f(n). This work is split into a different nodes (subproblems) and decreased by a factor of b until reaching the leaves. Since the problem is reduced by a factor of b, the height of the tree is
The total number of leaves is
since each level splits a times and this is done log base b of n times for each level. The base of the logarithm is b since the problem reduces by a factor of b, not a. Using some logarithm properties, the number of leaves can be reworked as follows:
Using what we have so far, we can derive the master theorem for each case in the table.
Case 1:
This means the work done at the root is polynomially smaller than the work done by the leaves. The additional work does not make much difference compared to the work done by the subproblems i.e. work increases as we go down the tree from the root. Because of this, the only work we need to consider is what is done at the final level where the leaves are since that is what dominates. In such a case, the total work can be computed by simply counting the number of leaves which turns out to be
Case 2:
This means the work done at the root is polynomially greater than the work done by the leaves. The subproblems do not require as much work as the additional work i.e. work decreases as we go down the tree. This causes the complexity of the root to overtake any work done at the other levels. For this case, we can simply ignore the leaves, leaving us with only f(n) and thus a complexity of
Case 3:
This means that the work done at each level is approximately the same at all levels. We know that the work at the leaf level is n to the power of log base b of a. However, since the work done at each level is basically the same, we need to repeat it by the number of levels. The number of levels is simply the height of the tree, log base b of n. Thus the total work done is the product of the height and the work done at the leaf level,
Another way of thinking about this is viewing aT(n/b) as the tree structure and f(n) as the weights of each node on the tree. When the complexity of the tree structure is greater than the weights of the nodes, then the tree structure dominates with the final complexity shown in case 1. When the node weights are greater than the tree, the former dominates with complexity O(f(n)) as shown in case 2. And when they are equal, both the tree and node weights contribute equally with the final complexity shown in case 3.
Well, what about cases when we don’t have such recurrence relations? When we have multiple recursive calls with different values of b? The Akra-Bazzi method can help us deal with some of these instances but not all of them. But there is another more general way of determining computational complexities. Since every recursion has a representative recursion tree, knowing how to analyze the complexity of a tree gives us a general approach to analyzing the complexity of any recursive program or recurrence relation. So as long as we can derive a recursion tree from our program or relation, we should be able to determine its complexity. Let’s try out some examples to see how we can derive computational complexities from recursion trees. Assuming we have the following recurrence relation,
we can derive the following recursion tree below.
Since only 1 is being removed at every recursive call and we have no repeated calls, the recursion tree only has a single branch. Because we keep subtracting 1 from n until reaching 1, we have a total of n nodes on the entire tree. Any recursive program with this recursive tree must iterate through the entire tree in order to solve the problem. Thus, the complexity of such a program should be the total work done by all of the nodes. That would be O(nf(n)) where f(n) is the work done by each node. When f(n) is a constant value, O(1), this turns into
which is the same complexity as computing a factorial since the recursive program for factorials shares a similar recurrence relation. When f(n)=O(n^k) i.e. a polynomial, the complexity is simply
since we are just adding an extra iteration of n. That’s basically the second case of the master theorem for linear recurrences (a=1) when both the recurrence and the additional work contribute equally.
Get Computing Macroxela’s stories in your inbox
Join Medium for free to get updates from this writer.
If it turns out that the tree structure does not contribute as much as the additional work, we can ignore the entire tree resulting in
as our complexity. That’s the first case of the master theorem (a<1) for linear recurrences. What if we subtracted by a value other than 1? It would not make much of a difference since we are still subtracting by a constant value. As long as we remove by a constant value, say something like f(n-k), and a ≤ 1, we will have a recursion tree without any branching of approximately height O(n). What about when we have some branching?
Analyzing another concrete example may give us better insight to the general so let’s go back to the Fibonacci sequence. That program has the following equation
which can be represented by the following recurrence relation
and results in the following recursive tree
The actual work is carried out on the leaves of this tree, all the other nodes rely on calls to the leaves with some constant work (O(1)). So we need to determine how many leaves this tree has. This tree has a branching factor of 2 so at the root (0th) level it has 1 node, at the 1st level it has 2 nodes, at the 2nd level 4 nodes and so on. Every level has a power of 2 number of nodes (2^0=1, 2^1=2, 2^2=4 and so on) with the power being the current level it is on. We can reasonably conclude that the number of leaves is a power of 2 as well
But what is the exponent? The recursive call always decreases by 1 or 2 until reaching fib(1) which means we need to subtract approximately n-1 times till we reach the final leaf. This results in a maximum depth (height) of n which results in 2^n leaves (technically not all of the leaves are at this level due to how the tree branches but the total number is still the same). Thus we have a complexity of O(2^n) for the recursive Fibonacci program.
Now we can generalize what we saw in the Fibonacci problem to other recursion trees.
For such cases, we need to consider how the branching impacts the recursion tree. Each node still has to carry out approximately f(n)=O(n^k) work. But now we need to multiply it by the number of leaves we have. How many leaves do we have with such branching? As we saw in the Fibonacci example, it should be a constant to some power of n. The Fibonacci sequence has a branching factor of a=2 which is why it has a power of 2. So a recursive tree with a branching factor of a should have a^n leaves. This is true if we simply subtract by 1 at every recursive call. We need to subtract 1 n times to get to the final leaf. That gives us a height of n for the tree. So what we actually have is
the branching factor to the power of the height of the tree. If we subtract by b instead, the height of the tree changes which results in a different power. For T(n-b), we need to subtract b at least k times to go through all n. This gives us the equation
which we can solve, giving us
Since we need to subtract n/b times, the tree has a height of n/b and thus a to the power of n/b leaves.
Where does this lead us? When the tree structure requires more work than what is carried out outside the recursive calls, we can just focus on the complexity of the tree itself giving us an overall complexity of
When the additional work is more than the actual tree (unlikely but may be the case), we can ignore the tree which gives us a complexity of O(f(n)). What is usually the case though is that both the recursive calls and the outside work contribute equally to the complexity which results in the 3rd case of the master theorem for linear recurrences,
We basically rederived the entire master theorem just by creating the recursive trees for recurrence relations and analyzing how they behave. And we were able to determine the complexities of recursive programs that do not fall under the master theorem. That’s the power of understanding how recursion trees work. It allows us to better understand how recursion affects the complexity of the program. It is not our only tool though. As stated before, there is the Akra-Bazzi method which allows us to analyze more general recurrence relations. This method requires a different kind of math than what we used here which we will explore in a later article.
If you want to delve deeper into this topic you can read the papers on the Master Theorem, including the original one, and the Divide and Conquer chapter in the Introductions to Algorithms by CLRS.
[1] A General Method for Solving Divide and Conquer Recurrences. Jon Louis Bentley, Dorothea Haken, James B. Saxe. https://dl.acm.org/doi/pdf/10.1145/1008861.1008865
[2] A Master Theorem for Discrete Divide and Conquer Recurrences. Micheal Drmota, Wojciech Sczpankowski. https://epubs.siam.org/doi/pdf/10.1137/1.9781611973082.28
[3] CMSC 351: The Master Theorem. Justin Wyss-Gallifent. https://www.math.umd.edu/~immortal/CMSC351/notes/mastertheorem.pdf
[4] Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. http://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
