Master Method

Master Method's statements

In the below equation, the constant a >= 1, b > 1 and f(n) is a function that’s always positive for some n > N > 0.

For the pattern of recurrence below.

T(n) = a * T(n / b) + f(n)

The case below that is satisfied determines our final answer.

1. If f(n) = O(n^logb(a)-ϵ), then T(n) = Θ(n^logb(a)).
2. If f(n) = Θ(n^logb(a)), then T(n) = Θ(n^logb(a) * log(n)).
3. If f(n) = Ω(n^logb(a)+ϵ), then T(n) = Θ(f(n)).

ϵ > 0 for the above equations. Let's discuss a few examples below.

Examples of Master Method

We'll take three examples below to help you get used to the Master's Method.

1. T(n) = 3 * T(n / 2) + n

In the above equation a = 3 >= 1, b = 2 > 1 and f(n) = n, once you compare it with th

Here, n^logb(a) is n^log2(3). log2(3) ≈ 1.58. f(n) < nlog2(3) - ϵ for some ϵ > 0.

Therefore, we follow case 1, and our answer is Ө(n^log2(3)).
 

2. T(n) = 4 * T(n / 2) + n²

In the above equation a = 4 >= 1, b = 2 > 1 and f(n) = n².

Here, n^logb(a) is n^log2(4). log2(4) = 2. f(n) = Ө(n²)

Therefore, we follow case 2, and our answer is Ө(nlog2(3) * log(n)).
 

3. T(n) = 3 * T(n / 2) + n²

In the above equation a = 3 >= 1, b = 2 > 1 and f(n) = n².

Here, n^logb(a) is n^log2(3). log2(3) ≈ 1.58. f(n) > n^{log2(3) + ϵ} for some ϵ > 0.

Therefore, we follow case 3, and our answer is Ө(n²).

Limitations of Master Method

1. T(n) must be monotonic. Example - If  T(n) = sin(n), then we cant use master method.
2. f(n) must be a polynomial function, e.g. f(n) can’t be 1 / n, etc. Master's Method can't solve the recurrence, T(n) = T(n / 2) + sqrt(n). There’s a catch for this one though and that’s when f(n) = Ө(n^logb(a)log^k(n)) (this is an additional case), here k >= 0. Then we have our answer as T(n) = Ө(n^logb(a)log^k+1(n)).
3. "a" or "b" must be constants, i.e., they can't be a dependent variable. We can't solve the recurrence T(n) = n * T(n/2) + 1 using Master's Method as a = n (as a is dependent on the input size i.e. n).

Also see, Morris Traversal for Inorder.

FAQs

1. What are recurrences and their uses?
 A recurrence can describe any sequence of elements in an array in terms of themselves. Recurrences are used in various branches of mathematics in addition to Computer Science (in time complexity analysis) their application in finding the bound for the number of trivial operations by an algorithm, such as Number Theory (Fibonacci sequence), Calculus (Euler's Theorem), etc.

An example of a recurrence,

T(N) = T(N/2) + 1, (n > 1)
T(1) = 1

2. Why should we learn about different methods for solving recurrences?
Many methods make it easier for us to solve particular problems. Depending on the requirement, they can also help us (depending on if we need a tight bound or just an upper bound), and there are recurrences where you may not apply specific methods.

For example, the Substitution method can solve essentially any recurrence.
 

3. What does O(g(n)), Ө(g(n)), Ω(g(n)) mean?
Here,

If f(n) = O(g(n)), then f(n) < c * g(n), ∀ n > N > 0 and some c > 0.

If f(n) = Ө(g(n)), then c2 * g(n) < f(n) < c1 * g(n), ∀ n > N > 0 and some c1, c2 > 0.

If f(n) = Ω(g(n)), then f(n) > c * g(n), ∀ n > N > 0 and some c > 0.
 

4. What is a polynomial function?
Polynomial functions are of the form, f(n) = a_nxⁿ + a_n-1x^n-1 + …. + a₂x² + a₁x + a₀. Here a_k is a real number, 0 <= k <= n. n must be the set of whole numbers (all natural numbers including 0). Therefore, f(n) = sqrt(n) isn’t polynomial and neither is f(n) = 1/n. However, f(n) = 0 is a polynomial.
 

5. What is a monotonic function?
It refers to a function that is either entirely non-increasing or entirely non-decreasing.

Key Takeaways

This article covers the Master Method, one of the easiest methods to find an asymptotic bound on a recurrence. Other methods to achieve similar objectives are Substitution, Iteration and Recursion Tree. To understand the blog better, refer to the article here about Understanding of Analysis of Algorithms and here about Asymptotic Notations.

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!