Prune and search (in italiano "sfoltisci e cerca") è un metodo per risolvere problemi di ottimizzazione ideato da Nimrod Megiddo nel 1983.[1]
L'idea alla base del metodo è una procedura ricorsiva, ad ogni passo della quale la taglia dell'input è ridotta (prune) di un fattore costante 0 < p < 1 {\displaystyle 0<p<1} . Esso è dunque un algoritmo del tipo divide et impera. Sia n {\displaystyle n} la taglia dell'input, T ( n ) {\displaystyle T(n)} sarà la complessità temporale di tutto l'algoritmo e S ( n ) {\displaystyle S(n)} la complessità temporale dell'operazione di sfoltimento, allora T ( n ) {\displaystyle T(n)} obbedirà alla seguente relazione di ricorrenza:
che si può provare, col metodo di Akra-Bazzi, avere soluzione T ( n ) = O ( 1 + ∫ 1 x S ( u ) u d u ) {\displaystyle T(n)=O(1+\int _{1}^{x}{\frac {S(u)}{u}}du)} , se | S ′ ( n ) | = O ( x c ) {\displaystyle |S'(n)|=O(x^{c})} , dove c è una costante.