Answers.Body: <p>I think the example you gave is inappropriate. This formula is derived from the summation formula of the geometric series, but the summation formula does not apply to the case where the common ratio is 1. so if b &gt; 1, the formula is correct.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-06-10T14:15:41.973Z
Answers.LastActivityDate: 2023-06-10T14:16:37.087Z
Answers.LastEditDate: 2023-06-10T14:16:37.087Z
Answers.UserDisplayName: Hari Seldon
Answers.Body: <p>To be fair I struggle too, to see a reason for it to be included.</p>
  <p>I'll try to argumentate: assume that the optimal path has length N and therefore you have costs <span class="math-container">$c_1,\dots,c_N$</span> all positive and bigger than some <span class="math-container">$\epsilon&gt;0$</span>. Such <span class="math-container">$\epsilon$</span> can't be bigger than the minimum between <span class="math-container">$c_1,\dots,c_N$</span>.</p>
  <p>Now, to need that <span class="math-container">$+1$</span> correction factor it should be possible that</p>
  <p><span class="math-container">$$\cfrac{c_1+\dots+c_N}{\epsilon}&lt;N$$</span></p>
  <p>Since <span class="math-container">$\epsilon&lt;min\{c_1,\dots,c_N\}$</span> I could try to prove instead that</p>
  <p><span class="math-container">$$\cfrac{c_1+\dots+c_N}{min\{c_1,\dots,c_N\}}&lt;N$$</span></p>
  <p>But you can divide both members by N and multiply by <span class="math-container">$min\{c_1,\dots,c_N\}$</span> obtaining that</p>
  <p><span class="math-container">$$\cfrac{c_1+\dots+c_N}{N}&lt;min\{c_1,\dots,c_N\}$$</span></p>
  <p>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 <span class="math-container">$\lfloor C^\star/\epsilon\rfloor$</span>.</p>
  <p>On the flip coin by the way when you compute that <span class="math-container">$\lfloor C^\star/\epsilon\rfloor$</span> 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 <span class="math-container">$O(\circ)$</span> keep in mind that if a function is an <span class="math-container">$O(b^k)$</span> then it's an <span class="math-container">$O(b^{k+c})$</span> for every <span class="math-container">$c&gt;0$</span> so although not necessary the book isn't technically wrong.</p>
  <p><strong>EDIT:</strong> Take all I said with a grain of salt, I'm a student, too and still have to take the AI exam</p>
  <p><strong>EDIT 2:</strong> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-01T15:51:28.037Z
Answers.LastActivityDate: 2021-12-01T17:34:57.407Z
Answers.LastEditDate: 2021-12-01T17:34:57.407Z
Answers.UserDisplayName: Baffo rasta
Body: <p>I am reading the book titled <a href="http://aima.cs.berkeley.edu/index.html" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach 4th ed</a> by Stuart Russell and Peter Norvig. According to the book, the complexity of uniform-cost search is as
  <span class="math-container">$$
  O(b^{1+\lfloor{C^*/\epsilon}\rfloor}),
  $$</span></p>
  <p>where <span class="math-container">$b$</span> is the branching factor (i.e. the number of available actions in each state), <span class="math-container">$C^*$</span> is the cost of the optimal solution, and <span class="math-container">$\epsilon &gt; 0$</span> is a lower bound of the cost of each action.</p>
  <p>My question is: Why is there is a 1 in the formula?</p>
  <p>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 <span class="math-container">$\epsilon = 1$</span>, so, <span class="math-container">$C^*$</span> will be <span class="math-container">$2$</span>. Therefore, the complexity will be <span class="math-container">$O(b^{2})$</span>. But, from the above formula, the complexity will be <span class="math-container">$O(b^{3})$</span>.</p>
  <p><a href="https://i.sstatic.net/oAccC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oAccC.png" alt="enter image description here" /></a></p>
  <p>PS. I know there is a similar question in <a href="https://stackoverflow.com/q/19204682/3924118">stackoverflow</a> and have read the answer. But there is a disagreement between the answers about the 1.</p>
  
Tags: <time-complexity><norvig-russell><uniform-cost-search>
Title: Why is there a 1 in complexity formula of uniform-cost search?
UserDisplayName: user153245
ThreadText: # Why is there a 1 in complexity formula of uniform-cost search?
  
  (Asked by: username_0 on 2021-11-13)
  
  I am reading the book titled [Artificial Intelligence: A Modern Approach 4th ed](http://aima.cs.berkeley.edu/index.html) 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})$.
  
  [![enter image description here](https://i.sstatic.net/oAccC.png)](https://i.sstatic.net/oAccC.png)
  
  PS. I know there is a similar question in [stackoverflow](https://stackoverflow.com/q/19204682/3924118) and have read the answer. But there is a disagreement between the answers about the 1.
  
  **Tags:** time-complexity, norvig-russell, uniform-cost-search
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2023-06-10. Score: 0
  
  I think the example you gave is inappropriate. This formula is derived from the summation formula of the geometric series, but the summation formula does not apply to the case where the common ratio is 1. so if b > 1, the formula is correct.
  
  
  ---
  
  ### Answer by username_2 on 2021-12-01. Score: 0
  
  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.
  
  
  ---
  
  