Calculate algorithmic complexity of my code

28 Views Asked by At

I need to calculate time complexity of the following code

I'm developing a community tracking framework. The latter works in the following way:

  • A set of snapshots is given, each containing static communities.
  • A communities similarity network is constructed, using as weight the overlap coefficient between members of communities belonging to different snapshots.
  • Once the similarity network is obtained, the first step of the Louvain algorithm is applied (modularity is optimized at the level of the nodes, which in this case correspond to the communities), without performing the next steps (aggregation and repetition).

Here is the code that builds the network:

network_dict = {}

for i in range(0, len(communities_static)):
    for i1 in range(0, len(communities_static[i])):
        comm1 = communities_static[i][i1]
        for j in range(i + 1, len(communities_static)):
            for j1 in range(0, len(communities_static[j])):
                comm2 = communities_static[j][j1]

                intersection = len(list(set(comm1).intersection(comm2)))
                union = (len(set(comm1)) + len(set(comm2))) - intersection
                sim = (float(intersection) / union)

                if sim > 0:
                    network_dict[' '.join([str(elem) for elem in comm1])] = {' '.join([str(elem) for elem in comm2]): {"weight": sim}}

Where communities_static is a list containing the static communities of each snapshot. To clarify, communities_static[i] contains the static communities at the i-th snapshot. In this way I compare the communities of snapshot i only with the communities belonging to snapshots subsequent to i.

What is the time complexity of this operation? Shouldn't it be O(c^2) where c is the number of communities, since I do all possible comparisons but at each iteration I perform fewer comparisons. Is it O(t * log(c)), where t is the number of snapshots?

What is the total complexity if I also consider Louvain's first step (which should be O(c) where c is the number of communities)?