# Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G.

My algorithm is as follows:

Generate all subgraphs of size k, and check each one to determine if it is a valid clique.

I'm trying to find the time complexity of my algorithm, but I'm stuck on how to show it as a function of all three n, m and k.

Where n is the number of vertices in the graph, m is the number of edges and k is the specified size we are looking for.

I need to answer the following:

1. How many subgraphs of size k can we generate, in Θ notation as a function of n, m and k? (and why is it so)
2. What is the worst case time complexity of the algorithm, in O notation as a function of n, m and k? (and why is it so)

so far, I have the following:

• there are O(n^k) subgraphs to check
• worst case run time of the algorithm is O(n^kk^2)
• because there are O(n^k) subgraphs to check, each of which has O(k^2) edges

but I need it bound it in terms of m, the number of edges in the graph as well.

There are $$\binom{n}{k}$$ sets of $$k$$ vertices out of $$n$$, to check that they are actually a clique you need to check $$\binom{k}{2}$$ pairs to see if they are edges, for a total of $$\binom{n}{k} \binom{k}{2}$$ edge checks. If you store the graph as an adjacency matrix, each check is $$O(1)$$. So in all:
\begin{align*} \binom{n}{k} \binom{k}{2} O(1) &= O(n^k) O(k^2) O(1) \\ &= O(n^k k^2) \end{align*}
You should check combination $$\binom{n}{k}$$ and each check need $$\mathcal{O}(n+m)$$ because you should check any subset of vertices with size $$k$$ form a complete graph or not, so overall running time is $$\binom{n}{k}\mathcal{O}(n+m)=\mathcal{O}\left(n^k(n+m)\right).$$