In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m + hlog h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+ hlogp) for the general parallel best-first B&B algorithm in PRAMCREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+ (H/P) log (H/P)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε,γ}, where ε= 1/──logh, and r is the largest branch number of the nodes in the state-space tree. In this paper, it is that that that that B & B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω (m + hlog h) of the running the lower bound Ω (M / p + hlogp) for the general parallel best-first B & B algorithm in PRAMCREW is proposed, where p is the number of processors available. p + H + (H / P) log (H / P)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B & B algorithm is put forward. The parallel algorithm is the fastest one as p = max {hε, γ}, where ε = 1 / --logh, and r is the largest branch number of the nodes in the state-space tree.