Bird
Raised Fist0

What is the worst-case time complexity of the iterative DFS approach that enumerates all paths from source to target in a DAG with n nodes, where the number of paths can be exponential?

medium🪤 Complexity Trap Q13 of Q15
Topological Sort - All Paths From Source to Target (DAG)
What is the worst-case time complexity of the iterative DFS approach that enumerates all paths from source to target in a DAG with n nodes, where the number of paths can be exponential?
AO(n * 2^n) accounting for path copying and stack operations
BO(2^n) due to exponential number of paths in worst case
CO(n!) because permutations of nodes are explored
DO(n^2) due to visiting each edge once
Step-by-Step Solution
  1. Step 1: Identify number of paths

    In worst case, number of paths can be exponential, roughly 2^n for DAGs with branching.
  2. Step 2: Analyze per-path cost

    Each path is stored and copied when pushed to stack, costing O(n) per path. Total time is O(n * 2^n).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Exponential paths times linear path length copying [OK]
Quick Trick: Exponential paths x linear path copying = O(n * 2^n) [OK]
Common Mistakes:
MISTAKES
  • Ignoring path copying cost
  • Confusing edge visits with path enumeration
Trap Explanation:
PITFALL
  • Option B looks correct but ignores linear cost per path for copying and stack operations.
Interviewer Note:
CONTEXT
  • Checks if candidate understands complexity beyond just counting paths, including path storage overhead.
Master "All Paths From Source to Target (DAG)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes