Real-time search algorithms interleave search with execution in order to accomplish a task ei~ciently. Deciding when to begin execution of the current best action is crucial for creating high a performance realtime search algorithm. This paper explores the question of when to commencexecution for an on-line search performed with limited computation. We ex- *mine Good’s ideslised algorithm for deciding when to begin execution and illustrate some of its llmltations. We then present a revised, idealised algorithm that removes some of these limitations. The revised algorithm has been used u s basis for an algorithm that makes on-the-fly decisions for a simplified robot courier tuk. Previous empirical results show that this new algorithm outperforms previously used alsorithms. In this paper, we show that the di~erence in performance is bounded by a ratio of two to one. We discuss the situations where this limit is approached and suggest that overlappins search with execution in these situations is most beneficial.