The average complexity of depth-first search with backtracking and cutoff

This paper analyzes two algorithms for depth-first search of binary trees. The first algorithm uses a search strategy that terminates the search when a successful leaf is reached. The algorithm does not use internal cutoff to restrict the search space. If N is the depth of the tree, then the average number of nodes visited by the algorithm is as low as O(N) and as high as O(2 N ) depending only on the value of the probability parameter that characterizes the search. The second search algorithm uses backtracking with cutoff. A decision to cut off the search at a node eliminates the entire subtree below that node from further consideration. The surprising result for this algorithm is that the average number of nodes visited grows linearly in the depth of the tree, regardless of the cutoff probability. If the cutoff probability is high, then the search has a high probability of failing without examining much of the tree. If the cutoff probability is low, then the search has a high probability of succeeding on the leftmost path of the tree without performing extensive backtracking. This model sheds light on why some instances of NP-complete problems are solvable in practice with a low average complexity.