[prev] 57 [next]

Divide-and-conquer

To solve a problem on a whole data structure ...
  • split the data structure into two parts
  • solve the problem on each part
  • combine results for parts
A general problem-solving strategy with wide application.

Typically produces elegant recursive solutions.

Depending on application, cost may be O(n) or O(log2n)