The Master Theorem
The first question before we start discussing is that why we will use master’s theorem?
While analyzing an algorithm our primary concern is on its run time complexity
finding the complexities of non-recursive functions is simpler,
for (i=1; i<=n; i++)
{statement;}
this is a simple one-line code and its complexity is simply n, but when it comes to finding the complexities of divide and conquer type recursive function following algorithms it becomes hard and often very much difficult that one is unable to find it.
Here master’s theorem comes into play. Master theorem help us calculate the execution time easily, it is a faster approach to find the complexities, it provides pre-defined formulas/equations, applying which we can directly find the complexities of such hard recurrence functions. All we need is to remember these equations by heart, a small silly mistake would make us do the inaccurate calculations and thus computing the wrong complexity!
The approach of Master’s theorem was first presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980 and named as “unifying method” for solving recurrence relations.
The master’s theorem is applied to the recurrence relations of the form-
T(n) = aT(n/b) + f(n),
where a>=1, b>1 and f is asymptotically positive.
Here, a problem takes “T(n)” amount of time, “n” is the size of the main problem, at every step we are dividing the problem into “a” different part each of size “n/b”. Since the problem is divided into subproblems so f(n) is the extra amount of work done to combine the problems.
The three basic rules for finding the complexities defined under the base master theorem:
(The notations used here i.e., Big-oh, theta and omega are your regular notations)
A refresher of The Asymptotic notations for better understanding:
Big-oh notation-
The function f(n)=Big-oh(g(n)) iff there exists positive constants c and no such that f(n)<=c*g(n) for all n>=no.
Omega notation-
The function f(n)=Omega(g(n)) iff there exists positive constants c and no such that f(n)>=c*g(n) for all n>=no.
Theta notation-
The function f(n)=Theta(g(n)) iff there exists positive constants c1, c2 and no such that c1*g(n) <=f(n)<=c2*g(n).
Now let us discuss some examples to gather better understanding of master theorem.
Example1: 4T(n/2) + n
Compare it with T(n) = aT(n/b) + f(n)
Here a=4, b=2, f(n)=n
Example2: 4T(n/2) + n²
Compare it with T(n) = aT(n/b) + f(n)
Here a=4, b=2, f(n)=n²
Example3: 4T(n/2) + n²/log n
Compare it with T(n) = aT(n/b) + f(n)
Here a=4, b=2, f(n)= n²/log n
Since the difference between f(n) and n^(logba) is non-polynomial difference, therefore the “basic” master theorem does not apply here.
To solve such type of problems an Extended Version of Master Theorem is developed.
It is a mixture of basic master theorem with some advanced version.
(note: b is base)
General Expression:
T(n) = aT(n/b) + θ((n^k)(logn)^p) — — (1)
The rules for Extended Master’s theorem:
- if a > b^k, then T(n) = θ(n^(logba))
- if a = b^k, then
(a) if p > -1, then T(n) = θ(n^(logba) (logn)^(p+1))
(b) if p = -1, then T(n) = θ(n^(logba) loglogn)
(c) if p < -1, then T(n) = θ(n^(logba)) - if a < b^k, then
(a) if p >= 0, then T(n) = θ((n^k) (logn)^p)
(b) if p < 0, then T(n) = θ(n^k)
Example:
T(n) = 2T(n/4) + n^(0.51)
Comparing with (1) we get:
a=2, b=4, k=0.51, p=0
2<=4^0.51 and p>=0
Therefore, using case3:
T(n)= θ(n^0.51)
Summary:
Finding the time complexities using the Extended Master Theorem is more-easy and time saving than basic one. The set of rules and equations provided by this theorem helps in faster calculation and thus saving time and energy of the programmer. The coder needs to write a code and ask for the input values required at run time and he will be getting the output in seconds. The pre-requisites required before studying master theorem are- one should have knowledge about recursive functions and basic time complexity for better understanding of this theorem.
References:
1) https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
2) https://fdocuments.in/document/introduction-to-algorithms-thomas-b-cormen.html
3) https://www.youtube.com/watch?v=OynWkEj0S-s&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=27
