Time complexity for finding the number of triangles in a graph

Question

In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using math or simply intuition. I am able to explain, how one of the complexities comes about, but not the other one. I haven't the slightest clue as to how, and I have been trying for hours now to understand that. So if someone could help me with a step by step explanation as to how the 2nd time complexity is what it is, I'd very much appreciate it.

We have a Graph $G=(V,E)$ where $|V|=n$ (nr. of nodes) and $|E|= m$ (nr.of edges)

We use the following pseudo-code initially, where G[u][v] is true iff there is an edge between u and v.

 1  function count_triangles (Adjacent Matrix G[][])   
 2    count:=0   
 3    for u in V do
 4      for v in V do
 5        for w in V do
 6          if (G[u][v] and G[v][w] and G[u][w]) then
 7              counter = counter + 1
 8          end
 9        end
10        end    
11      end   
12    return count / 6
13  end

In the worst case scenario, that of a complete graph, we'd get a time complexity of $\Theta(n^3)$ in order to find all the triangles. The reason being: You have a set of $n$ nodes. You consider an initial one out of $n$. Then for the next one you have $n-1$ possibilities to choose, and for the 3rd one you have $n-2$ possibilities to choose from. That means: $n*(n-1)*(n-2)$, which belongs to $\Theta(n^3)$.

Now a second pseudocode was given, as follows:

function count_triangles_2 (Adjacent Matrix)   

 1  function count_triangles_2 (Adjacent Matrix)   
 2    count:=0   
 3    for u in V do
 4      for v in V do
 5         if not G[u][v] then continue 
 6         for w in V do
 7           if (G[v][w] and G[u][w]) then
 8              counter = counter + 1
 9           end
10         end
11       end    
12    end   
13    return count / 6
14  end

Now regarding this pseudo-code. Like the above one, in the worst case scenario, that of complete graph, the time complexity is the same. But when the graph is thin, i.e the number of edges is linear compared to the nr. of nodes, maybe a bigger value then $n$ but still linear, in this case the time complexity is $\Theta(n*m)$.

I want to know how the fact that we consider a thin graph, must help me into find $\Theta(n*m)$. I want to understand the thinking process that goes behind this. How should my view of this problem change, with the information that the graph is thin, where $m>n$. What I see in the 2nd pseudo-code is that we have 2 for loops, one is nested. The first one iterates at least through $\frac n 2$ elements, and the 2nd loop, iterates at least through $\frac n 2 -1$ elements. This means that we get something proportional to $n^2$.

And one more thing: Initially we said for the 2nd pseudo-code that the time complexity is $\Theta(n^2 + n*m)$. I understand that this is the case where we have nodes that are not adjacent to other nodes, or that the number of nodes is compare-able to the nr. of edges, because we are having a forest and not a tree. But if we consider the case that the graph is connected and that $m>n$, then $\Theta(n^2 + n*m) \rightarrow \Theta(n*m)$. But as I said, I don't understand how we find $\Theta(n*m)$.

Answer 1

Let us look at the count_triangles_2.

The time it takes to run the function is spent mostly on executing line $5, 6, 7, 8, 9$ and $10$.

So, the time-complexity is about $$n_5 * \text{time}(\text{line 5}) + n_{678910} * \text{time}(\text{line 6, 7, 8, 9, 10})$$ where $n_5$ is the number of times line 5 will be executed and $n_{678910}$ is the number of times lines $6, 7, 8, 9$ and $10$ as a block will be executed.

$n_5 = n^2$.
$\text{time}(\text{line 5})=\Theta(1)$
$n_{678910}=2m$ since line 6 will be run iff (u,v) is an edge.
$\text{time}(\text{line 6, 7, 8, 9, 10})=\Theta(n)$

Hence, the time-complexity is $$n^2\Theta(1) + 2m\Theta(n)=\Theta(n^2+2mn)=\Theta(mn),$$ where the last step assumes $m\ge n$.