Estimate time complexity of a graph algorithm

Question

I have an undirected graph G = (V, E) represented by an adjacency matrix. For each edge I must compute its weakness. The weakness d is computed as follow:

Where Nx is the set of direct nodes of x (with direct nodes I mean the nodes with a path of 1 from x).
I've wrote this algorithm, but I'm not sure about how to evaluate its complexity.

float **graph_weakness(struct graph *g)
{
    int i;
    int j;
    int n = g->n;
    struct edge *edge;
    int rel_union;
    int rel_intersect;
    int idx;
    float **m = graph_to_matrix(g);

    /* complessità: O(|V|/2|E|) */
    for (i = 0; i < n; i++) {
        edge = g->nodes[i]->edges;
        while (edge != NULL) {
            idx = edge->idx;
            if (m[i][idx] == MATRIX_SET) {
                rel_union = 0;
                rel_intersect = 0;
                for (j = 0; j < n; j++) {
                    if (m[i][j] != 0.0 || m[idx][j] != 0.0) {
                        rel_union++;
                    }
                    if (m[i][j] != 0.0 && m[idx][j] != 0.0) {
                        rel_intersect++;
                    }
                }
                m[i][idx] = 1 - (float) rel_intersect / rel_union;
                m[idx][i] = m[i][idx];
            }
            edge = edge->next;
        }
    }

    return m;
}

The algorithm iterates over the edges and for each edge computes the intersection and union of the sets using a loop from 1..|V|.
Tha matrix is symmetric so the computation is made on half the edges.
The complexity should therefore be O(|E|/2 * |V|) = O(|E|*|V|), am I right?

"Where Nx is the set of direct edges of node x." - what does that mean? The edges emanating from x? Terminating at x? — Ami Tavory
Sorry I mean "the set of direct nodes of x" (with direct nodes I mean the nodes with a path of 1 from x). — raxell

Ami Tavory Ami Tavory · Accepted Answer · 2016-02-16T12:13:07

The line

float **m = graph_to_matrix(g);

is probably Θ(|V| |E|)

(it depends on your matrix library).

(Perhaps somewhat contrary to the statement in your question), the algorithm starts by looping over all nodes

for (i = 0; i < n; i++) {

For each node, it iterates over all neighbors

while (edge != NULL) {

and for each neighbor, it iterates over all nodes again

for (j = 0; j < n; j++) {

So, assuming your graph has adjacency-list representation, this first + second loop are run O(|E| + |v|) times altogether, and each iteration iterates over |V| items.

This algorithm is O((|E| + |V|) |V|), therefore.

Estimate time complexity of a graph algorithm

1 Answers