Question: the complexity with solution at depth k and branching factor...
The complexity with solution at depth k and branching factor b for iterative deepening,
b^k + (b/b-1)^2
with b − 1. on the denominator is not a good approximation when b ≈ 1. Give a better estimate of the complexity of iterative deepening when b ≈ 1. (Hint: think about the case when b = 1.) How does this compare with the A∗ for such graphs? Suggest a way that iterative deepening can have a lower overhead (less complexity) when the branching factor is close to 1.