I think that the number of positions that need to be considered for a brute force exhaustive search are roughly proportional to an exponential function of the n

I think that the number of positions that need to be considered for a brute force exhaustive search are roughly proportional to an exponential function of the number of moves made, so the statement holds true for that. In reality, the number of possible moves is not constant and depends on the current position.