Divide-and-Conquer (DnC)

Recursively, many algorithms try to call themselves multiple times for solving tightly relevant sub-problems.

The DnC paradigm takes the following steps:

  1. DIVIDE original problem into sub-problems

  2. CONQUER each sub-problem recursively

  3. (*) COMBINE solutions for sub-problem into one for the original problem

    Note: some problems don't have combination phase; for instance, BinarySearch will search for specified element in either the left (n /2) or the right (n /2) of an array and return that element if found.

Table of Contents

  • Multiplication - chapter about integer multiplication, matrix multiplication and polynomial multiplication.

  • Master Method - a generalized form of mathematical interpretation is given for DnC problems.

  • DnC Strategy - several different strategies for various problems will be covered.

PreviousAsymptotic-AnalysisNextOverview

Last updated