What is the time complexity of the following algorithm on graphs

Question

Consider undirected graph with $O(n)$ nodes and $O(m)$ edges. We store the edges in adjacent list, so for each node we keep list of the nodes such there exist edge between those nodes.

Our search goes as follows: For each node in the graph (let it be i) we iterate over all pairs of nodes(let it be $n_1 \text{ and } n_2$) such that there is edge between $i \text{ and } n_1 \text{ and between } i \text{ and } n_2$.Let's just analyze the complexity of those iterations.

Here is the pseudo code to make sure everything is understood well

for each node i in graph G:
    for each node n1 in adjacent list of i:
        for each node n2 in adjacent list of i:
            O(1) work here

From first look it looks like $O(n^3)$ since there are three nested loops, however I don't think that this is correct. What is the correct way to analyze the time complexity here?

Answer 1

For every $v$, there are $\binom{n-1}{2}$ pairs in the worst case that need to be checked, since $v$ may be connected up to $n-1$ other vertices.

Since $\binom{n-1}{2} = \Theta(n^2)$, your algorithm performs $O(n^2)$ queries for every vertex. Since there are $n$ vertices, the time complexity is $O(n^3)$ and your analysis is correct.

---

Suppose we want to express the algorithm cost in terms of $m$.

For every $v_i$, we perform work equal to the number of neighbours over 2 of $v$, denoted by $N_i$. Or $\binom{N_i}{2}$

It is clear that the runtime would be $O(N_1(N_1-1) + N_2(N_2-1) +\dots +N_n(N_n-1))$ $$ = O(\sum_{i=1}^n (N_i)(N_i-1)$$

We know that $\sum_{i=1}^n (N_i) = 2m$, since every arc is counted exactly twice. What is left is to prove $$\sum_{i=1}^n (N_i)(N_i-1) = O(nm)$$

Since $N_i \leq n-1$ it follows: $$\sum_{i=1}^n (N_i)(N_i-1) \leq \sum_{i=1}^n (N_i)*n = n\sum_{i=1}^n (N_i) = n*2m=O(nm)$$

Answer 2

Because the given undirected graph $G$ has $a=O(n)$ nodes and $b=O(m)$ edges, the time-complexity of the algorithm depends on both $a$ and $b$.

Let $v_1, \cdots, v_a$ be the vertices. The degree of vertices Let the degree of $v_i$ be $d_i$ and $f(G)=v_1^2+v_2^2+\cdots+v_n^2$. Then the time-complexity of the algorithm on $G$ is $$t(G)=O(f(G)).$$

What is the worst case for the algorithm? It happens when all edges are concentrated on as few nodes as possible.

• If $b\le a-1$, then it should be a star graph plus extra isolated vertices. The degree sequence is $(b, 1, 1, \cdots, 1)$. $f(G)=b^2+b$.
• If $b= c(a-c)+ \frac{c(c-1)}2=c(a-1)-\frac{c(c-1)}2$, then the degree sequence should be $(a-1, a-1, \cdots, a-1, c, c,\cdots,c)$, where the number of $(a-1)$'s is $c$ and the number of $c$'s is $a-c$. $f(G)=c(a-1)^2 +(a-c)c^2\le ba$.

So, $f(G)=O(b\min(b,a)).$

$$t(G)=O(f(G))=O(b\min(b,a)).$$

That is the (worst) time-complexity of the algorithm. If we have to use $m$ and $n$ instead of $a$ and $b$, then $O(m\max(m,n))$ is the time-complexity. In case when $a=n$ and $b=m$, the worst time-complexity is simply $O(m\min(m,n))$.