All about Master Theorem with its Proof!
Introduction: This is the best method(shortcut)/technique to find the Time Complexity of any algorithm by its recurrence relation.
Master Theorem
The version of the master theorem is applicable only if the recurrence relation is in the form:
- where a ≥ 1, b≥1, d≥ 0
There are 3 cases for the master theorem:
Case 1: d < log(a) [base b] => Time Complexity = O(n ^ log(a) [base b])
Case 2: d = log(a) [base b] => Time Complexity = O((n ^ d) * log(n) )
Case 3: d > log(a) [base b] => Time Complexity = O((n ^ d))
Proof Of Master Theorem
The above form of master theorem expresses that the problem is in the form of tree and the tree is formed as show below:
Also, we all know that if a problem can be represented in the form of tree as above, it goes to at-most to level log(n)[base b]. At this level we left with 1, that is we have divided to the problem to the shortest problem possible.
Work done at each level is represented as:
Note: There is one correction in the last line of the above image, it should be “log(n)[base b]” instead of “log(b)[base n]”.
Before I provide to proof each case of master theorem, there are some concepts which I need to clear, and they are explained below:
- In a Geometric series, as each next element in the series differ by a common multiple integer, conventionally, we take it as “r”.
- Sum of the Geometric series is formula is a * ( (1-r^n) / (1–r) ), where a is the first term.
Proof of Case 1; d < log(b) [base a]:
- The above case can also be understood as the work done is increasing in each of the subsequent levels of the tree.
- Also, it is the case when r < 1 in a Geometric series, so, in this case, the major term will be the last term of the geometric series which will be having the maximum effect.
- So, in the total work done formula we take to take only the last term, i.e. substitute k = log(n) [base b] in the time complexity expression.
This expression requires log properties to solve, so please study that.
We got the result which we have said before. Hence Proved.
Proof of Case 2; d= log(b) [base a]:
It means that the work done in each of the levels is equal, so we can easily obtain the final work done by multiplying the number of levels and work done on each level.
Hence Proved.
Proof of Case 3; d > log(a) [base b]:
This means that that the work required is constantly decreasing in the subsequent levels => Work done in the first level is the maximum => We need to consider only the first term.
This clearly provides O(n^d).
Hence Proved.
I hope you guys enjoyed the article and easily understood the proof of Master Theorem which is always confusing.
