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?

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

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

  • $\begingroup$ 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)$? $\endgroup$ May 11, 2019 at 9:35
  • $\begingroup$ I'm kind of trying to find out if this time complexity depends on the number of edges $m$ and if so, how. $\endgroup$ May 11, 2019 at 9:40
  • $\begingroup$ @someone12321 It is, it can be written as $O(nm)$. added proof in edit $\endgroup$
    – lox
    May 11, 2019 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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