3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Just a terminology note: problems have complexity; algorithms have running times and space usage. $\endgroup$ – David Richerby May 11 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$ – Apass.Jack May 11 at 14:23
3
$\begingroup$

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

$\endgroup$
  • $\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$ – someone12321 May 11 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$ – someone12321 May 11 at 9:40
  • $\begingroup$ @someone12321 It is, it can be written as $O(nm)$. added proof in edit $\endgroup$ – lox May 11 at 14:25
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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