Core Java

Master Theorem

1. Introduction

An algorithm is a well-defined instruction set designed to solve a particular problem for the given input data sets

Master theorem refers to the fact that you can solve a problem in a divide-and-conquer way to provide an asymptotic analysis. We can use this in the analysis of many divide and conquer algorithms.

This algorithm was firstly presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980, where it was presented as a unifying method for solving recurrence problems. Cormen, Leiserson, Rivest, and Stein introduce this concept in their book: Introduction to Algorithms where became famous under the name: master theorem.

2. What is Master Theorem?

This method is used to solve recurrence relations. The formula describing this method is:

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

The meaning of each parameter, where a>= 1, b >1:

  • n – size of input
  • a – number of subproblems in the recursion
  • n/b – size of each subproblem (assume that all subproblems have the same size)
  • f(n) – time to create the subproblems and combine their results in the above procedure

Master Theorem is a very useful and when it comes to design and analysis for divide and conquer technique. Above all mentioned, the master theorem provides the solution in asymptotic terms (time complexity) for recurrence relations. The recurrence relation is dependent on the previous runs.

3. Solved Examples with Master Theorem

Examples solved with master theorem.

3.1. Case Example 1

T(n) = 8T(n/2) + n2

Where the parameters are (taking into consideration the base formula):

a = 8; b = 2; f(n) = n2

f(n) = O(nc); c= 2

logb a = log2 8 = 3 > c;

T(n) = O (nlogb a) = O(n3)

3.2. Case Example 2

T(n) = 2T(n/2) + n

a = 2, b = 2, c = 1, f(n) = n;

f(n) = O(nc + logkn), where c= 1; k = 0;

logb a = log2 2 = 1. What we can see is that c = logb a;

T(n) = O(nlogb a logk+1 n) = O(n1 log1n) = O (n log n);

Thus the given recurrence relation T(n) was in O(n log n).

3.3. Case Example 3

T(n) = 2T(n/2) + n2

a = 2, b = 2, f(n) = n2

f(n) = Omega(nc), where c = 2;

logb a = log2 2 = 1, and therefore, yes, c > logb a where, T(n) = O(f(n)) = O (n2).

The recurrence relation T(n) was in O(n2) and compiles with f(n) of the original formula.

More information with practice problems you can find here.

4. Master Theorem Limitations

Likewise other algorithms the Master Theorem has some limitations that are not efficient and cannot be used in some cases.

The limitations are:

  • T(n) is not monotone
    T(n) = T(n/2) + n (2 – cos n) => regularity violation.
  • f(n) is not a polynomial
    T(n) = 2 T(n/2) + n/ log n => non-polynomial difference f(n) and nlogb n.
  • a is not a constant
    T(n) = 2n T(n/2) + nn => a is not a constant (subproblem size should be fixed).
  • this method cannot be used if f(n), the combination/merging time is not positive. f(n) should be positive.
    T(n) = 64T(n/8) – n2 log n => f(n) combination time, which is not positive.
  • the value of a should be constant and always greater than 1.
    T(n) = 0.5T(n/2) + n => a < 1 cannot have less than 1 problem.
  • the value of b should be greater than 1.

5. Time complexity

Time complexity of an algorithm is the efficiency that the given set of instructions can solve the problem. In other words, time complexity is a concept in Computer Science that deals with quantification of the amount of time taken by the set of code to process or run as a function for the given input set.

The most common time complexity in computer science are:

  • O(1) – constant. This is when accessing a specific element from an array.
  • O(n) – linear. Looping through an array of elements.
  • O(log n) – logarithmic. Finding an element in a sorted array.
  • O(n2) – quadratic. Looping for in for.
  • O(2n) – exponential. Double recursion in Fibonacci.

For the most important algorithms the time complexity calculated with master theorem is:

  • Binary search. T(n) = T(n/2) + O(1). With time complexity of: O(log n)
  • Binary tree transversal. T(n) = 2T(n/2) + O(1). With time complexity of: O(n).
  • Optimal sorted matrix sort. T(n) = 2T(n/2) + O(log n). With time complexity of: O(n)
  • Merge sort. T(n) = 2T(n/2) + O(n). With time complexity of: O(n log n).

The time complexity grows as the input grows. Best practice time complexity are below O(n), which are: O(log n) or O(1).

6. Java examples

For instance, let’s write a simple java example for the master theorem. We will show you a Java example to prove the Master Theorem with Merge Sort.

Dividing the input into subproblems
    /**
     * Merge and sort the array
     *
     * @param inputArray the given input array to sort
     * @param beginning  the beginning of the array
     * @param end        the end index of the array
     */
    private static void mergeAndSort(int[] inputArray, int beginning, int end) {
        if(beginning < end) {
            int midOfArray  = (beginning + end) / 2;
            mergeAndSort(inputArray, beginning, midOfArray);
            mergeAndSort(inputArray, midOfArray + 1, end);
            merge(inputArray, beginning, midOfArray, end);
        }
    }

    public static void main(String[] args) {
        final int[] customArray = new int[]{5, 10, 2, 8, 1, 20, 9, 4};
        mergeAndSort(customArray, 0, customArray.length - 1);
        System.out.println("The sorted array is: " + Arrays.toString(customArray));
    }

The output of the above snippet code:

The sorted array is: [1, 2, 4, 5, 8, 9, 10, 20]

Process finished with exit code 0

If you want to run this class from cmd line you can execute this command in the root of the project (that you downloaded from the download section):

java src/MergeSort.java

I just added just a part of the code. If you want to see the full code please download it from the below section.

7. Final note

As a last note about this article, I could say that this theorem can be used in many day-to-day tasks to solve recurrence problems.

To sum up, the ideas presented in this article were to introduce you to the concept of the Master Theorem with a bit of knowledge about how it starts and the person who invented this concept.

Likewise in other articles, we have some examples with this theorem to better understand the concept.

Download
You can download the full source code for this article here: Master Theorem

Iulian Timis

My name is Iulian and I graduated Faculty of Electronics, Telecommunications, and Information Technology. My master's degree was in Computer Science, Information Security. I am passionate about technology and the security area. During my career I was working as a Java Developer, on the backend and frontend side, sometimes doing some DevOps tasks.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button