In the solution, we iterate through both the edges and nodes separately. Shouldn’t the time complexity be O(n + m) where n is number the nodes and m is the number of edges? Or does it get adjusted to just O(n) because we know the number of edges is approximately the same as the number of nodes?
Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: Solution: Graph Valid Tree
Hello @Michael_D,
You are correct in mentioning that the time complexity should be O(N + E), where N is the number of nodes and E is the number of edges. Since, every node and edge is visited once. N is the number of nodes. The complexity is linear with respect to the total number of nodes and edges.
Thank you for pointing this out, we’ll make the changes as suggested. Also, feel free to share further suggestions and feedback. We’d be happy to hear!
Happy learning!