The complexity of my algorithm is in $O(\frac{p^p}{p!}(\frac{n}{p})^k)$ for any $p=o(n)$ and $k>1$.How can I simplify this complexity while removing this $p$?For instance, for $p=2$ the complexity is in $O((\frac{n}{2})^k)$, but for $p=3$ it is in $O((\frac{n}{3})^k)$ which is better.Can I have a formula without fixing $p$ and that would be always the best?
Simplifying a parametrized complexity given that a parameter is in $o(n)$
parameterized complexity
I've discussed with an ``FPT and XP guy'', we found that I shouldn't have written the problem in such a way. Let me rewrite it.This is related to graph algorithms. Chiba and Nishizeki showed that it is possible to list $(k+2)$-cliques (cliques on $k+2$ nodes) in time $O(m \cdot a^k)$ 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.pdfWe have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^k}{k!})$.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}{k!})$ is better than $O(m \cdot a^k)$?For instance, does it make sense to write: $m \cdot \frac{(2a)^k}{k!}\leq m \cdot \frac{4^4}{4!}\cdot (\frac{a}{2})^k$ and thus the running time of our algorithm is in $O(m \cdot (\frac{a}{2})^k)$ and is thus better than the one of Chiba and Nishizeki?If what is above is ok, then as I've done this with $p=4$, why can't I do it with $p=1000$?