Why is there a 1 in complexity formula of uniform-cost search?

Question

I am reading the book titled Artificial Intelligence: A Modern Approach 4th ed by Stuart Russell and Peter Norvig. According to the book, the complexity of uniform-cost search is as $$ O(b^{1+\lfloor{C^*/\epsilon}\rfloor}), $$

where $b$ is the branching factor (i.e. the number of available actions in each state), $C^*$ is the cost of the optimal solution, and $\epsilon > 0$ is a lower bound of the cost of each action.

My question is: Why is there is a 1 in the formula?

For example, suppose in the following tree, the red node is the initial state and the green one is the goal state, and two actions are needed to reach the goal state from the initial state. If the cost of both actions is equal to $\epsilon = 1$, so, $C^*$ will be $2$. Therefore, the complexity will be $O(b^{2})$. But, from the above formula, the complexity will be $O(b^{3})$.

PS. I know there is a similar question in stackoverflow and have read the answer. But there is a disagreement between the answers about the 1.

Answer 1

To be fair I struggle too, to see a reason for it to be included.

I'll try to argumentate: assume that the optimal path has length N and therefore you have costs $c_1,\dots,c_N$ all positive and bigger than some $\epsilon>0$. Such $\epsilon$ can't be bigger than the minimum between $c_1,\dots,c_N$.

Now, to need that $+1$ correction factor it should be possible that

$$\cfrac{c_1+\dots+c_N}{\epsilon}<N$$

Since $\epsilon<min\{c_1,\dots,c_N\}$ I could try to prove instead that

$$\cfrac{c_1+\dots+c_N}{min\{c_1,\dots,c_N\}}<N$$

But you can divide both members by N and multiply by $min\{c_1,\dots,c_N\}$ obtaining that

$$\cfrac{c_1+\dots+c_N}{N}<min\{c_1,\dots,c_N\}$$

On the left hand side you have the average of the costs, which of course can't be smaller than the minimum of the costs, therefore that has no solution. This means that even without the +1 factor you can't underestimate the length of the path to the optimal solution using $\lfloor C^\star/\epsilon\rfloor$.

On the flip coin by the way when you compute that $\lfloor C^\star/\epsilon\rfloor$ you're actually trying to find an upper bound for the length of the optimal path, so if you add +1 (equivalent to compute the ceiling instead of floor) you still get an upper bound. Also, since you're computing an $O(\circ)$ keep in mind that if a function is an $O(b^k)$ then it's an $O(b^{k+c})$ for every $c>0$ so although not necessary the book isn't technically wrong.

EDIT: Take all I said with a grain of salt, I'm a student, too and still have to take the AI exam

EDIT 2: I thought that another possible reason why you would expand (at most) b more nodes after reaching the depth of the optimal goal is that you perform the goal test the moment you extract the node from the frontier and not before insertion. This is necessary cause it grants us that when we extract a node from the frontier we reached it through the path with lowest cost from the initial state, but it will cause us to expand at most one more level before realizing a node in the frontier is indeed a goal.