I'm currently learning about graphs and have been studying Depth-First Search (DFS).
I understand that the worst-case time complexity of DFS is O(n + m).
I also know that the maximum number of edges in a graph is m = n(n - 1)/2, (i.e., a complete graph).

Based on this, my intuition tells me that in the worst case, m = O(n^2), so the complexity of DFS perhaps should be: O(n + n^2) = O(n^2).

This seems much "scarier" than O(n + m), so my question is: Why don't we just say the worst-case complexity of DFS is O(n^2)? Am I missing something?

I'm currently learning about graphs and have been studying Depth-First Search (DFS).
I understand that the worst-case time complexity of DFS is O(n + m).
I also know that the maximum number of edges in a graph is m = n(n - 1)/2, (i.e., a complete graph).

Based on this, my intuition tells me that in the worst case, m = O(n^2), so the complexity of DFS perhaps should be: O(n + n^2) = O(n^2).

This seems much "scarier" than O(n + m), so my question is: Why don't we just say the worst-case complexity of DFS is O(n^2)? Am I missing something?

• algorithm
• data-structures

• Why don't you just say it's O(n!)? That's even scarier. – no comment Commented Feb 1 at 22:02
• The worst case is when no nodes have multiple children, ie basically a linked list – Bohemian ♦ Commented Feb 1 at 22:23
• @Bohemian That's a best case. – no comment Commented Feb 1 at 23:00

2 Answers 2

You only have to assume the maximum number of edges only if you don't know what kind of graph you're working with. If you already know the number of edges, you can give a much more precise worst case time complexity for the search. This is useful e.g. when comparing different algorithms that would run on the same graph, and allows you to distinguish the algorithms that work well only on graphs with few edges.

I would prefer to use |