What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?
The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is
$$
\sum_{k=0}^n n(n-1)\cdots(n-k+1) = \sum_{k=0}^n \frac{n!}{(n-k)!} = n! \sum_{k=0}^n \frac{1}{k!} \approx e \cdot n!.
$$
When the maximum clique has size $k$, the number of recursive calls is at most
$$
1 + n + n(n-1) + \cdots + n(n-1)\cdots(n-k+1) \leq 2n^k.
$$
Conversely, if you run the algorithm on a complete $k$-partite graph, then the number of recursive calls will be $\Omega(n^k)$.