Divide and Conquer - Intuitive understanding of Master theorem

Today we will discuss about Master Theorem, in an intuitive way.

Divide and Conquer is a way to solve the problem by dividing the problem space recursively and adding up the solutions to get the complete solution. Merge sort uses this approach to solve the problem of Sorting. Given a problem, how can we make sure divide and conquer would help to solve that. For instance, finding a minimum in a set of numbers of cardinality n, can be solved in O(n) using naive approach. Can we use divide and conquer approach to solve this problem? Ok, that won't be efficient, in fact make your program run slow rather than naive approach in practical. Which makes divide and conquer not usable for some problems. Answer lies in Master theorem which makes asymptotic analysis of certain recurrence relations easy. Let us formally analyse the complexity of Merge sort and Finding minimum.

Merge Sort:

T(n) = 2 T(n / 2) + Ө(n), Ө(n) is the complexity of merging results from divided problem spaces, in this case problem space is divided by two recursively.

Let us try to expand T(n),

T(n) = 2 T(n/2) + n, Ө has been eliminated for ease of understanding.

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

= 8 T(n/8) + 4 * n/4 + 2 * n/2 + n

....

= n ^{log ₂ 2} T(n/ n ^{log ₂ 2}) + ~nlog ₂ n

= n + nlog ₂ n, T(1) is assumed as 1 here.

Finally, T(n) is Ө(n log ₂ n), since n * log ₂ n dominates.

In case of our contrived example of finding minimum using divide and conquer would give

T(n) = n + 1 * log ₂ n

So, it would be Ө(n) since n dominates.

Let us define the general recurrence relation, T(n) = a T(n / b) + f(n)

Intuitively, T(n) would be the dominating one among n ^{log _b a} and f(n) as per the discussion above.

Master theorem formulates the above general problem, in three cases as given below.

Case 1:

If f(n) = O( n ^{log _b a-e}) for some constant e > 0, then T (n) = Θ( n ^{log _b a}).

Intuitively n ^{log _b a} dominates f(n), hence T(n).

Case 2:

If f(n) = Θ( n ^{log _b a} log ^k n) with k ≥ 0, then T (n) = Θ(n ^{log _b a} log ^k+1 n),

You could correlate the results from above merge sort analysis with this.

Case 3:

If f(n) = Ω( n ^{log _b a+e}) for some constant e > 0, then T (n) = Θ( f(n) ). It needs a condition that, a * f(n/b) <= c f(n).

This is again, an inverse condition of Case 1. Important thing to note is the condition. If the condition is not satisfied, f(n) might be f(n) log _b n.

So, the bottom line is Complexity analysis of Divide and Conquer can be easily done with Master theorem. As an exercise, you could try analysing Binary search algorithm using Master theorem method.

One important thing to note is Master theorem applies, if and only if f(n) is polynomial.

Thanks for reading. Suggestions and Questions are welcome.