Bird
Raised Fist0

What is the worst-case time complexity of building the graph and performing a DFS-based topological sort in the Alien Dictionary problem, given N words with total length C, U unique characters, and E edges?

medium📊 Complexity Q5 of Q15
Topological Sort - Alien Dictionary (Infer Character Order)
What is the worst-case time complexity of building the graph and performing a DFS-based topological sort in the Alien Dictionary problem, given N words with total length C, U unique characters, and E edges?
AO(E^2)
BO(U * E)
CO(C * U)
DO(C + U + E)
Step-by-Step Solution
Solution:
  1. Step 1: Graph construction time

    Comparing adjacent words takes O(C) time total to find edges.
  2. Step 2: DFS topological sort time

    DFS visits each node and edge once, O(U + E).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Graph build plus DFS traversal sums to linear in input size [OK]
Quick Trick: Graph build plus DFS is linear in input size [OK]
Common Mistakes:
MISTAKES
  • Assuming quadratic complexity due to nested loops
  • Ignoring the linear scan of words for graph edges
  • Confusing unique characters with total characters
Trap Explanation:
PITFALL
  • Misunderstanding that graph edges are fewer than total characters
Interviewer Note:
CONTEXT
  • Tests knowledge of complexity analysis for graph algorithms
Master "Alien Dictionary (Infer Character Order)" 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