Expected search duration for finite backtracking adaptive search

Backtracking adaptive search is an optimisation algorithm which generalises pure adaptive search and hesitant adaptive search. This paper considers the number of iterations for which the algorithm runs, on a problem with finitely many range levels, in order to reach a sufficiently extreme objective function level. A difference equation for the expectation of this quantity is derived and solved. Several examples of backtracking adaptive search on finite problems are presented, including special cases that have received attention in earlier papers.