<p>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.</p>

<p>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.<br>
<a href="http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J053.pdf" rel="nofollow noreferrer">http://www.ecei.tohoku.ac.jp/alg/nishizeki/sub/j/DVD/PDF_J/J053.pdf</a></p>

<p>We have designed an algorithm that can do it in time $O(m \cdot \frac{(2a)^k}{k!})$.<br>
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.<br>
So the question is, how can we show that $O(m \cdot \frac{(2a)^k}{k!})$ is better than $O(m \cdot a^k)$?</p>

<p>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?</p>

<p>If what is above is ok, then as I've done this with $p=4$, why can't I do it with $p=1000$?</p>

CC BY-SA 3.0
2017-03-03T22:20:56.573Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2017-03-03T22:31:32.723Z
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).
Saeed
CC BY-SA 3.0
2017-03-03T23:30:14.843Z
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...
maxdan94
CC BY-SA 3.0
2017-03-05T04:57:41.487Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-03-03T17:46:10.877Z
2017-03-03T23:44:46.723Z
2017-03-03T23:44:46.723Z
maxdan94
<p>Thanks a lot for your comment, I think it can be an answer.</p>

<p>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?</p>

<p>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!})$.</p>

<p>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?</p>

CC BY-SA 3.0
2017-03-02T18:46:03.793Z
2017-03-03T14:42:21.820Z
2017-03-03T14:42:21.820Z
maxdan94
<p>The complexity of my algorithm is in $O(\frac{p^p}{p!}(\frac{n}{p})^k)$ for any $p=o(n)$ and $k&gt;1$.<br>
How can I simplify this complexity while removing this $p$?</p>

<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.<br>
Can I have a formula without fixing $p$ and that would be always the best?</p>

CC BY-SA 3.0
2017-03-02T17:15:20.330Z
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!)$.
Emil Jeřábek
<parameterized-complexity>
Simplifying a parametrized complexity given that a parameter is in $o(n)$
maxdan94
# Simplifying a parametrized complexity given that a parameter is in $o(n)$

(Asked by: username_0 on 2017-03-02)

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?

**Tags:** parameterized-complexity

> **Comments:**
> **username_1**: 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!)$.  

---

## 2 answers

### Answer by username_0 on 2017-03-03. Score: 0 | Accepted answer

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

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

> **Comments:**
> **username_2**: 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$.  
> **username_3**: 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).  
> **username_0**: 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...  
> **username_2**: 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.  

---

### Answer by username_0 on 2017-03-02. Score: 1

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?


---

