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