0
$\begingroup$

I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.

enter image description here

For BFS it is intuitive to me that we take the exponent of each level of depth since we are expanding all nodes.

For IDDFS, the equation to my understanding is looking at the deepest level, taking the breadth of that (d)b since it was only looked at once, then the level prior to that (d-1) needs to have its nodes expanded twice, hence it is b^2.

Then after the ... we are multiplying breadth by 3, to the power of depth-2? (i.e 3b^d-2).

Is someone able to explain this? Also any recommendations for sources that give a clear breakdown of what is happening? Just seeing formulas restated isn't helping on my learning journey, would be great to find a source that talks it through and/or gives a visual breakdown.

$\endgroup$
1
  • $\begingroup$ Not every traversal is a search, and while I see how Richard E. Korf called it iterative deepening, I'm dumbfounded by the depth first part for a traversal by level in DFID. $\endgroup$
    – greybeard
    Mar 9, 2023 at 7:50

1 Answer 1

0
$\begingroup$

You can read the details of the analysis of the algorithm here.

But the idea is that, the target node will be found at depth $d$, with respect to a specified source/root node. Then this node, along with all other nodes with the same depth, will be visited once, and there are at most $b^d$ of them. That accounts for the last term in your summation. Now moving backwards, the parents of these nodes will be visited twice - once when the algorithm sets the depth to $d-1$, and another when the depth is set to $d$. The number of such nodes is at most $b^{(d-1)}$, which gives the $2b^{(d-1)}$ term. You can continue this until you get to the nodes at depth 1, which will be visited $d$ times and there are at most $b$ of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.