iterative deepening depth first search higer time complexity than depth first search?

Question

It seems that iterative deepening search should have a higher asymptotic time complexity than BFS because every time the depth-limit is increased, it must start its search from the beginning.

But wiki says otherwise, why?

Answer 1

If the tree is not balanced and the answer lies nearer to the root than the deepest leaf, then the answer will be found by a depth-limit which is less than the maximum depth of the tree, whereas depth first search may have to search half of the tree to the maximum depth before it finds the right answer. Since the number of nodes in the tree may grow roughly exponentially with the depth, this might be a good bargain - with maximum depth 10, searching roughly 1024/2 = 512 nodes is slightly more expensive than multiple searches totalling 1 + 2 + 4 + ... 256 = 511 nodes, so anything more extreme than that is pure profit - and that example searches depths up to and including depth 8 completely.

(And in some cases there may be wrong answers at arbitrarily large depths).