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?

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) = n2m=O(nm)$$

StackExchange Computer Science Q#109221, answer score: 3