depth-first-iterated-deepening search vs depth-first search

Question

I actually don`t have a question concering coding, but search algorithms, I hope this is ok. In an assignment I need to solve the following question:

"Describe a state space in which dfid is much worse than dfs, e.g., O(n²) vs. O(n)." dfid is depth-first-iterated-deepening search and dfs normal depth-first search. I`m not sure how to solve this problem, I know that the worst case runtime is like O(b^d) for both searches in trees, but I find it hard to actually find a good example.

I thought about a tree with a branching of only 2, since the lower the branching the worse for dfid runtime.

Can somebody help me out with this?

Answer 1

If your state space is like a linked list (i.e. only 1 child per node) and the goal state is the leaf, you will end up with exactly the situation you described.

With DFS, you will proceed along each child until you reach the leaf. If there are n nodes, the running time is O(n).

With IDS, in the first iteration you will only visit the child of the root. In the second iteration, you will visit the root's child and its own child (depth = 2, visited 2 nodes). In the third iteration, you go to a depth of 3, visiting 3 nodes. Hence the total number of visits is 1 + 2 + .... + n = O(n^2).