Comparing the complexity of algorithms for listing k-cliques Chiba and Nishizeki showed that it is possible to list all $k$-cliques (cliques on $k$ nodes) in time $O(m \cdot a^{k-2})$ where a is the arboricity of the graph and $m$ the number of edges in the graph. http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J053.pdf

We have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$.
In practice, on real-world graphs (which have a small arboricity), our algorithm performs much better than the one of Chiba and Nishizeki. We now want to show through theory that it is better.
So the question is, how can we show that $O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is better than $O(m \cdot a^{k-2})$?
Note that we are interested in instances of small $k$, say 10 or less. Is the big O notation relevant here? Or should we work with upper bounds and lower bounds on the number of operations (quantifying the constants in the big O)?
$O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is not necessarily better than $O(m \cdot a^{k-2})$, since the big-oh notation $O$ is an upper bound. To compare the two algorithms, you'd better analyze using the $\Theta$ notation. In addition, note that if you set $k$ to some fixed value, terms such as $\frac{2^{k-2}}{(k-2)!}$ are considered to be constants and thus omitted in asymptotic analysis.