The time complexity analysis of the IDA* algorithm has shown that predicting the growth of the search tree essentially relies on only two criteria: The number of nodes in the brute-force search tree for a given depth and the equilibrium distribution of the heuristic es- timate. Since the latter can be approximated by random sampling, we accurately predict the number of nodes in the brute-force search tree for large depth in closed form by analyzing the spectrum of the problem graph or one of its factorization. We further derive that the asymptotic brute-force branching factor is in fact the spectral radius of the problem graph and exemplify our consid- erations in the domain of the (n^2-1)-Puzzle.