Why is Iterative deepening ok?
Suppose increment = 1, solution at depth d
- how much more work do we expect to do in I.D. vs DF ?
I.d. repeats work from depths 1 to d
?di=1 bi = b d+1 / (b - 1)
Ratio to b d = b d+1 / bd(b - 1) = b/(b-1)
So we only do b/(b-1) times as much work as we need to
- e.g. even if b=2, only do twice as much work
Very often worth the overhead for the advantages