cancel
Showing results for 
Search instead for 
Did you mean: 

Weakly Connected Components Complexity

Cobra
Ninja
Ninja

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

1 ACCEPTED SOLUTION

Cobra
Ninja
Ninja

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.

View solution in original post

1 REPLY 1

Cobra
Ninja
Ninja

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.