# Why does this algorithm work in O(n m)?

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)

• 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. Jan 27, 2015 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 27, 2015 at 9:29
• Added these details Jan 27, 2015 at 9:39
• The complexity is both O(n*m) and O(n^2) because m is a linear function of n. Jan 27, 2015 at 10:08

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) Jan 27, 2015 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 27, 2015 at 10:18