Weakly Connected Components Complexity

[Cobra]

Hello,

I would like to know the Time and Space complexity of the Weakly Connected Components algorihtm implementation in Neo4j. I could not find these information in the documentation or in the GitHub.

Feedback: Moreover, would it be possible to add these information for all the algorithms in GDS?

Regards,
Cobra

[Cobra · Accepted solution]

Thank you @abk for the answer:

For a directed Graph G(V,E), it has a time complexity of O(|E|) and a space complexity of O(|N|), so linear in both space and time. Some concrete numbers: r5d.16xlarge, twitter dataset (~60M nodes, 1.4B edges), 64 threads. wcc runs in 4.55 seconds if the graph is loaded directed and 1 second if its loaded as undirected.