What is Master's theorem?
Master’s theorem is one of the many methods that are applied to
calculate time complexities of algorithms. In analysis, time complexities
are calculated to find out the best optimal logic of an algorithm.
Master’s theorem is applied on recurrence relations.
But before we get deep into the master’s theorem, let us first revise what
recurrence relations are −
Recurrence relations are equations that define the sequence of
elements in which a term is a function of its preceding term. In
algorithm analysis, the recurrence relations are usually formed when
loops are present in an algorithm.
Problem Statement
Master’s theorem can only be applied on decreasing and dividing recurring functions. If the relation is not decreasing or
dividing, master’s theorem must not be applied.
Master’s Theorem for Dividing Functions
Consider a relation of type
T(n) = aT(n/b) + f(n)
where, a >= 1 and b > 1,
n − size of the problem
a − number of sub-problems in the recursion
n/b − size of the sub problems based on the assumption that all sub-problems are of the same size.
f(n) − represents the cost of work done outside the recursion -> Θ(nk logn p) ,where k >= 0 and p is a real number;
If the recurrence relation is in the above given form, then there are three cases in the master theorem to determine the
asymptotic notations
•If a > bk , then T(n)= Θ (nlogb a ) [ logb a = log a / log b. ]
•If a = bk
• If p > -1, then T(n) = Θ (nlogb a logp+1 n)
• If p = -1, then T(n) = Θ (n logb a log log n)
• If p < -1, then T(n) = Θ (n logb a)
•If a < bk,
• If p >= 0, then T(n) = Θ (nk logp n).
• If p < 0, then T(n) = Θ (nk)
Master’s Theorem for Decreasing Functions
Consider a relation of type
T(n) = aT(n-b) + f(n) where, a >= 1 and b > 1, f(n) is asymptotically positive
Here,
n − size of the problem
a − number of sub-problems in the recursion
n-b − size of the sub problems based on the assumption that all sub-problems are of the same size.
f(n) − represents the cost of work done outside the recursion -> Θ(n k), where k >= 0
If the recurrence relation is in the above given form, then there are three cases in the
master theorem to determine the asymptotic notations −
•if a = 1, T(n) = O (nk+1)
•if a > 1, T(n) = O (an/b * nk)
•if a < 1, T(n) = O (nk)
Example 1
Consider a recurrence relation given as T(n) = 8T(n/2) + n 2
In this problem, a = 8, b = 2 and f(n) = Θ(nk logn p) = n2,
giving us k = 2 and p = 0. a = 8 > bk = 22 = 4,
Hence, case 1 must be applied for this equation.
To calculate,
T(n) = Θ (nlogb a ) = nlog28 = n( log 8 / log 2 ) = n3
Therefore, T(n) = Θ(n3) is the tight bound for this equation.
Consider a recurrence relation given as T(n) = 4T(n/2) + n 2
In this problem, a = 4, b = 2 and f(n) = Θ(nk logn p) = n2,
giving us k = 2 and p = 0. a = 4 = bk = 22 = 4, p > -1
Hence, case 2(i) must be applied for this equation.
To calculate,
T(n) = Θ (nlogb a logp+1 n) = nlog24 log0+1n = n2logn
Therefore, T(n) = Θ(n2logn) is the tight bound for this
equation.
Consider a recurrence relation given as T(n) = 2T(n/2) + n/log n
In this problem, a = 2, b = 2 and f(n) = Θ(nk logn p) = n/log
n, giving us k = 1 and p = -1. a = 2 = bk = 21 = 2, p = -1
Hence, case 2(ii) must be applied for this equation.
To calculate, T(n) = Θ (n logb a log log n) = nlog44 log logn
= n.log(logn)
Therefore, T(n) = Θ(n.log(logn)) is the tight bound for this
equation.
Consider a recurrence relation given as T(n) = 16T(n/4) + n 2/log2n
In this problem
a = 16, b = 4 and f(n) = Θ(nk logn p) = n2/log2n, giving us k = 2 and
p = -2. a = 16 = bk = 42 = 16, p < -1
Hence, case 2(iii) must be applied for this equation.
To calculate,
T(n) = Θ (n logb a) = nlog416 = n2
Therefore, T(n) = Θ(n2) is the tight bound for this equation.
Few examples to apply master’s theorem in decreasing recurrence
relations −
Consider a recurrence relation given as T(n) = T(n-1) + n 2
In this problem, a = 1, b = 1 and f(n) = O(nk) = n2, giving us k
= 2.
Since a = 1, case 1 must be applied for this equation.
To calculate, T(n) = O(nk+1) = n2+1 = n3
Therefore, T(n) = O(n3) is the tight bound for this equation.
Consider a recurrence relation given as T(n) = 2T(n-1) + n
In this problem, a = 2, b = 1 and f(n) = O(nk) = n, giving us k
= 1.
Since a > 1, case 2 must be applied for this equation.
To calculate, T(n) = O(an/b * nk)
= O(2n/1 * n1)
= O(n2n)
Therefore, T(n) = O(n2n) is the tight bound for this equation.
Consider a recurrence relation given as T(n) = n4
In this problem, a = 0 and f(n) = O(nk) = n4, giving us k = 4
Since a < 1, case 3 must be applied for this equation.
To calculate,
T(n) = O(nk) = O(n4) = O(n4)
Therefore, T(n) = O(n4) is the tight bound for this equation
