Prune and search is a method of solving optimization problems suggested by Nimrod Megiddo in 1983.
[1] 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.
In prune and search algorithms S(n) is typically at least linear (since the whole input must be processed).
This can be seen either by applying the master theorem for divide-and-conquer recurrences or by observing that the times for the recursive subproblems decrease in a geometric series.
In particular, Megiddo himself used this approach in his linear time algorithm for the linear programming problem when the dimension is fixed[2] and for the minimal enclosing sphere problem for a set of points in space.