title: Time complexity of Uniform-cost search
body: <p>I am reading the book <em>Artificial Intelligence: A Modern Approach</em>. I came across this sentence describing the time complexity of uniform cost search: </p>
  
  <blockquote>
    <p>Uniform-cost search is guided by path costs rather than depths, so its
    complexity is not easily characterized in terms of b and d. Instead,
    let C be the cost of the optimal solution, and assume that every
    action costs at least ε. Then the algorithm’s worst-case time and
    space complexity is O(b^(1+C/ε)), which can be much greater than b^d.</p>
  </blockquote>
  
  <p>As to my understanding, C is the cost of the optimal solution, and every action costs at least ε, so that C/ε would be the number of steps taken to the destination. But I don't know how the complexity is derived.</p>