Time complexity of \(A^{**}\)

Abstract. This paper focuses on the time complexity of three famous heuristic graph-search algorithms, namely the algorithm \(A^*\), \(B\) and \(A^{**}\), and analyzes their executions. The concept of the super-threshold will be introduced which draws attention to certain steps of the executions of the graph-search algorithms. It will be shown that the states of the executions of \(A^*\), \(B\) and \(A^{**}\) at these moments are identical and the executions of these algorithms can differ at most between two such adjacent moments. Thereafter a secondary tie-breaking rule for the algorithm \(A^{**}\) will be defined in order for this algorithm to be better than the other two.