1
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yes you are right for the $\Theta$, I'm not sure I can prove a $\Theta$ or a relevant $\Omega$ though. Your second comment is precisely my concern, I think I should drop the big-oh notation and somehow reason on the number of flops in order to show that one algorithm requires less flops than the other one. Any comment on that? $\endgroup$
    – maxdan94
    Mar 4 '17 at 15:30
  • $\begingroup$ @maxdan94 You may show your algorithm is better than the other's in the worst case. That is, you first show that the other algorithm can be $\Omega(m \cdot a^{k-2})$ in the worst case. This would suggest that your algorithm is asymptotically better since $O(\frac{2^{k-2}}{(k-2)!}) = o(1)$ for general $k$. Alternatively, you can run some experiments on some real graphs to compare two algorithms. $\endgroup$
    – PSPACEhard
    Mar 4 '17 at 15:35
0
$\begingroup$

I do not think that the big-oh notation is relevant in my case. As I'm interested in the running time when $a$ and $k$ are small, I will upper bound and lower bound the number of operations as a function of $m$, $k$ and $a$ without using the big-oh notation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.