master method

Solving Recurrences – Master Method

Introduction This post is to be read in continuation to the Divide and Conquer methodology for e.g. the Merge Sort problem. This post is an extension over the problem of solving recurrences or recurrence equations. There are several ways of solving recurrences namely Substitution Method, Master Method and Recurrence Tree method. The most confusing one or may I say relatively complex one is the Master Theorem. Here we will discuss the same. Master Theorem What does it solve? Not all the recurrences can be solved using the Master Theorem, but it still solves a large family of recurrences....
Read More