1

This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m)

This is a graph problem, where we are supposed to find the number of ways to traverse from a to c. Note that only the paths like a-->b-->c and a-->d-->c need to be considered. That is, there should be a difference of only one node, in between them.

n is the number of vertices, m is the number of edges and nxt is the adjacency list.

Let's iterate through all combinations of a and c just two simple nested loops in O(n^2) and find all candidates for b and d inside. To find candidates you can go through all neighbors of a and check that they are neighbors of c. Among all the candidates you should choose two junctions as b and d. So just use https://en.wikipedia.org/wiki/Combination All you need is to add to the answer , where r is the number of candidates (common neighbors of a and c). The code is:

for (int a = 0; a < n; a++)
    for (int c = 0; c < n; c++)
        if (a != c)
        {
            int r = 0;
            for (int b = 0; b < nxt[a].size(); b++)
                if (nxt[a][b] != a && nxt[a][b] != c && g[nxt[a][b]][c])
                    r++;
            result += r * (r - 1) / 2;
        }

It is easy to see that the total complexity is O(nm), because of sum of number of neighbors over all junctions is exactly m.

If there are 3 loops involved, then how can the worst case complexity be O(n m)

  • 1
    We need a bit more context to know what m is, and what assumptions have been made about nxt[a].size(). I'm guessing that the author has assumed that nxt[a] is of roughly constant size for all a. – Julia Hayward Jan 27 '15 at 9:23
  • I am assuming that n is number of vertices, m is number of edges as per usual convention and the nxt array is adjacency list of the graph. – Jan Hudec Jan 27 '15 at 9:29
  • Added these details – Dhruv Mullick Jan 27 '15 at 9:39
  • The complexity is both O(n*m) and O(n^2) because m is a linear function of n. – Pieter B Jan 27 '15 at 10:08
3

The outer loop has n iterations.

The middle loop has n iterations.

The inner loop has deg(a) iterations. This is because the nxt array is adjacency list of the graph, which means nxt[a] is a list of all edges going from vertex a and therefore nxt[a].size() is (out) degree of a.

Because m, the number of edges, is ∑a deg(a), the inner two loops together make m iterations and times the outer n is the result.


Notes: The test whether edge from nxt[a][b] to c exists is O(1), because g is incidence matrix. It is a bit unusual to see both adjacency list and incidence graph representations, because they both have to be prepared. The usual approach is to use adjacency list for sparse graphs, i.e. those with m ~ O(n), because then deg(a) ~ O(1) and linear search in the for the follow-up edge is constant-time, and to use incidence matrix for dense graphs, i.e. those with m ~O(n2), because then the O(n m) = O(n3) anyway, so looping over all vertices instead of out edges in the inner loop does not matter.

The other issue is that the author of this should be condemned for the choice of variables. It is usual for mathematical algorithms to use single-letter variables, but at least variable indicating index into the adjacency list should not be taken from the same range as variables for vertices. I'd use customary u and v for vertices (that is u = a and v = c) and i for index (that is i = b).

  • I agree that the operation r++ can be executed at max nm times. But won't b++ be executed n^2 m times? (Worst case) – Dhruv Mullick Jan 27 '15 at 9:42
  • @DhruvMullick: Number of iterations means the number that the third clause in the for is executed. The point is that maximum for b is number of edges from a, which is O(m/n), not m. – Jan Hudec Jan 27 '15 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.