Prune and search

Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983.

The basic idea of the method is a recursive procedure in which at each step the input size is reduced ("pruned") by a constant factor 0 < p < 1. As such, it is a form of decrease and conquer algorithm, where at each step the decrease is by a constant factor. Let n be the input size, T(n) be the time complexity of the whole prune-and-search algorithm, and S(n) be the time complexity of the pruning step. Then T(n) obeys the following recurrence relation: