# Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?

• Try drawing particular examples and see what you get. For example, if the branch factor is 2 then you have a binary tree. How many nodes does a binary tree of depth $d$ contain? And so on. Give it a few hours. – Yuval Filmus Feb 17 '17 at 8:17