ABSTRACT
This chapter revisits the divide-and-conquer paradigms and explains how to solve recurrences, in particular, with the use of the “master theorem.” We first illustrate the concept with Strassen’s matrix multiplication algorithm (Section 2.1) before explaining the master theorem (Section 2.2) and finally providing techniques to solve recurrences (Section 2.3). These techniques are further illustrated in the exercises of Section 2.4, with solutions found in Section 2.5.
