DFS Time Complexity

Link to a question: https://cses.fi/problemset/task/1666
Guide’s answer: https://usaco.guide/silver/dfs?lang=cpp

What is the time complexity of DFS:

  • For Loop that trys every node -> O(N)
  • DFS Loops through the adjacent list -> O(N)
  • DFS Checks if the node has already been visited -> O(1)

So I think it’s O(N^2), but I feel that that’s pretty large so I’m assuming I made a mistake.

Please let me know!

every vertex is visited at most 1 time

1 Like

DFS has a time complexity of O(n)

\mathcal{O}(N+M)

2 Likes

@Benq what is M?

in the question you linked

M is edges, N is nodes.

1 Like

Ohh Thanks!