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?

  • 1
    $\begingroup$ Parameterized complexity doesn’t mean what you think it means. Anyway, this is not a research-level question, it would be more suitable for math.stackexchange.com as it is just simple calculus. Use Stirling approximation for $p!$ and then minimize the expression with respect to $p$ by taking derivatives. You should get $O(n^k/k!)$. $\endgroup$ Mar 2 '17 at 17:15

Thanks a lot for your comment, I think it can be an answer.

I have this practical algorithm and I'm trying to express its running time as a function of some parameters and not only the size of the input. If parametrized-complexity is not the right keyword, could you help me to understand what is parametrized-complexity and to find the right keyword?

Following what you said, I have: $O(\frac{p^p}{p!}(\frac{n}{p})^k)=O(\frac{e^p}{\sqrt{p}\cdot p^k}n^k)=O(\frac{1}{\sqrt{k}}(\frac{e\cdot n}{k})^k)$. If now I replace p by k in the original formula, I have $O(\frac{n^k}{k!})$.

So I can claim (i) the complexity of the algorithm is in $O((\frac{n}{4})^k)$, (ii) the complexity of the algorithm is in $O(\frac{1}{\sqrt{k}}(\frac{e\cdot n}{k})^k)$ and (iii) the complexity of the algorithm is in $O(\frac{n^k}{k!})$. Is that correct?


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.

We 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$?

  • 1
    $\begingroup$ I don't understand why you are making this so complicated. $\frac{(2a)^k}{k!} \le a^k$ because $2^k \le k!$ for any $k$; moreover $2^k$ is a lot smaller than $k!$ even for modestly large $k$. $\endgroup$ Mar 3 '17 at 22:20
  • 1
    $\begingroup$ As Sasho mentioned, you simply can say your algorithm running time is much better than the other one, no one will complain (If those numbers are correct). $\endgroup$
    – Saeed
    Mar 3 '17 at 22:31
  • $\begingroup$ I'm not happy because (i) it seems that I can write that the algorithm is in $O(m\cdot (\frac{a}{1000})^k)$ and that $O(m\cdot (\frac{a}{1000})^k) \subsetneq O(m\cdot \frac{(2a)^k}{k!})$ and (ii) I'm interested in the running time when k is not too large, maybe the big O notation is not what I want... $\endgroup$
    – maxdan94
    Mar 3 '17 at 23:30
  • 1
    $\begingroup$ You need to think for yourself what it is you want to show. What is "not too large"? Do you want $k$ bounded by a fixed constant? Or $k$ growing to infinity with $n$ but much more slowly, say at the rate of $\log n$? There are some modeling questions only you know the answers to. $\endgroup$ Mar 5 '17 at 4:57

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