Is it correct to state that the space complexity of Depth-First Search (DFS) is $O(bm)$ and that of Iterative Deepening Depth-First Search (IDDFS) is $O(d)$?

Here, $b$ represents the branching factor, $m$ the maximum depth, and $d$ the depth reached by iterative deepening. If I provide definitions for these two algorithms, can I then accurately apply these complexity measures?

  • $\begingroup$ @greybeard I don't think space complexity and number of operations are equal. $\endgroup$
    – rus9384
    Commented May 29 at 16:47


Your Answer

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