In the worse case, union-find is O(m log n) and BFS/DFS is O(n + m) right?
Then the union-find has strictly worse worst case execution time no?
In practice, where the graph is sparse, the union-find can be much faster, but here I am only talking about big O time.
Correct me if I am wrong.
I have the similar questions when I learn Union-Find algorithm since lots of problems seem faster if using DFS/BFS over union-find.
But StackOverflow has 2 great posts regarding DFSvsUF:
2.For time complexity, please check Runtime analysis: DFS vs. Union-Find for computing connected components of a static graph
I quote the conclusions:
a. "For static graph, DFS; Dynamic graph, Union-Find"
b. "That said, union-find is helpful only if edges and vertices are never deleted."
c. "Union-find has an extra multiplicative factor α(V), which makes it slower than DFS asymptotically (and probably practically as well)."