# Hypergraph sorting computational complexity

For a hypergraph, I want to know the computational complexity of this step in my algorithm what is the computational complexity of this kind of sorting

Sort the hyperedges in descending order based on the number of common vertices with other hyperedges

I implement this step by calculating the degree of each vertex (the number of hyperedges it belongs). Then, for each hyperedge, I count the number of vertices that have degree greater than one and order the hyperedges

So the time complexity is $$O(M+|\mathcal{E}|K_c+ |\mathcal{E}|)$$ is it correct assuming that we have M vertices

• The complexity depends on how you implement this step. Jun 7 '19 at 6:03
• I implement this step by calculating the degree of each vertex (the number of hyperedges it belongs). Then, for each hyperedge, I count the number of vertices that have degree greater than one and order the hyperedges. Jun 7 '19 at 8:39
• You should update your question with the complete details. Jun 7 '19 at 9:23
• @YuvalFilmus Formally speaking, the complexity is a property of the problem; the actual running time achieved depends on the algorithm used. Jun 7 '19 at 11:19
• @DavidRicherby so my answer is incorrect? any advice about how to figure out this kind of sorting Jun 7 '19 at 11:29