# What is the time complexity of the following algorithm on graphs

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?

• Just a terminology note: problems have complexity; algorithms have running times and space usage. – David Richerby May 11 '19 at 11:00
• "Consider undirected graph with $O(n)$ nodes and $O(m)$ edges". Why not just $n$ nodes and $m$ edges? – John L. May 11 '19 at 14:23

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)$$

• I understand this, however since there are $O(m)$ edges, in worst case of complete graph it would be that $O(n^2) = O(m)$, so the time complexity would be $O(nm)$? – someone12321 May 11 '19 at 9:35
• I'm kind of trying to find out if this time complexity depends on the number of edges $m$ and if so, how. – someone12321 May 11 '19 at 9:40
• @someone12321 It is, it can be written as $O(nm)$. added proof in edit – lox May 11 '19 at 14:25

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))$$.

• Hmm, I did not see the update to the other answer. My result is only better when the graph is not connected. – John L. May 11 '19 at 14:44
• Since my answer does not provide any real extra value beyond the accepted answer, it will be deleted shortly. – John L. May 12 '19 at 1:50