CS Notes

This site uses Just the Docs, a documentation theme for Jekyll.

Search

Divide-and-conquer

“Veni, vidi, vici. (I came, I saw, I conquered.)”― Julius Caesar

Table of contents

  1. Introduction
  2. References

Introduction

Divide-and-conquer algorithms involve three steps:

  1. Divide the problem into smaller subproblems.
  2. Conquer the subproblems by solving them recursively.
  3. Combine the solutions to the subproblems into the solution for the original problem.

[1, P. 65]

When a subproblem is large enough to be solved recursively, it’s called the recursive case [1, P. 65].

When a subproblem becomes small enough that the algorithm no longer recurses (the recursion “bottoms out”), it is called the base case [1, P. 65].

Merge sort is an example of a divide-and-conquer algorithm.

References

  1. [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009.