Master Theorem
Master’s method is a quite useful method for solving recurrence equations because it directly gives us the cost of an algorithm with the help of the type of a recurrence equation and it is applied when the recurrence equation is in the form of:
T(n) = aT(n/b) + f(n)where, a≥1, b>1 and f(n)>0
Contents
Introduction
proof the Master Theorem
limitation
Introduction
Many algorithms have a runtime of the form
where is the size of the input and and
are constants with
asymptotically positive. For instance, one ca that runtime of the merge sort algorithm satisfies
Similarly, traversing a binary tree takes time
By comparing
to the asymptotic behavior of
, the master theorem provides a solution to many frequently seen recurrences.
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.
Solved 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.
.
Master Theorem Limitations
The master theorem cannot be used if:
- T(n) is not monotone. eg.
T(n) = sin n f(n)is not a polynomial. eg.f(n) = 2n- a is not a constant. eg.
a = 2n a < 1
