Design and Analysis - Master’s Theorem

Master’s theorem is one of the many methods that are appped 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 appped 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 appped on decreasing and spaniding recurring functions. If the relation is not decreasing or spaniding, master’s theorem must not be appped.

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 > b^k , then T(n)= Θ (n^{logb a} ) [ log_b a = log a / log b. ]

If a = b^k

If p > -1, then T(n) = Θ (n^{logb a} log^p+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 < b^k,

If p >= 0, then T(n) = Θ (n^k log^p n).

If p < 0, then T(n) = Θ (n^k)

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 (n^k+1)

if a > 1, T(n) = O (a^n/b * n^k)

if a < 1, T(n) = O (n^k)

Examples

Few examples to apply master’s theorem on spaniding recurrence relations −

Example 1

Consider a recurrence relation given as T(n) = 8T(n/2) + n²

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 appped 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.

Example 2

Consider a recurrence relation given as T(n) = 4T(n/2) + n²

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 appped 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.

Example 3

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 appped 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.

Example 4

Consider a recurrence relation given as T(n) = 16T(n/4) + n²/log²n

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 appped for this equation.
To calculate, T(n) = Θ (n logb a)
   = nlog416
   = n2
Therefore, T(n) = Θ(n2) is the tight bound for this equation.

Example 5

Consider a recurrence relation given as T(n) = 2T(n/2) + n²

In this problem, a = 2, b = 2 and f(n) = Θ(nk logn p) = n2, giving us k = 2 and p = 0.
a = 2 < bk = 22 = 4, p = 0
Hence, case 3(i) must be appped for this equation.
To calculate, T(n) = Θ (nk logp n)
   = n2 log0n
   = n2
Therefore, T(n) = Θ(n2) is the tight bound for this equation.

Example 6

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) = n3/log n, giving us k = 3 and p = -1.
a = 2 < bk = 23 = 8, p < 0
Hence, case 3(ii) must be appped for this equation.
To calculate, T(n) = Θ (nk)
   = n3
   = n3
Therefore, T(n) = Θ(n3) is the tight bound for this equation.

Few examples to apply master’s theorem in decreasing recurrence relations −

Example 1

Consider a recurrence relation given as T(n) = T(n-1) + n²

In this problem, a = 1, b = 1 and f(n) = O(nk) = n2, giving us k = 2.
Since a = 1, case 1 must be appped 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.

Example 2

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 appped 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.

Example 3

Consider a recurrence relation given as T(n) = n⁴

In this problem, a = 0 and f(n) = O(nk) = n4, giving us k = 4
Since a < 1, case 3 must be appped 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.