-2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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$
    – Emil Jeřábek
    Commented Mar 2, 2017 at 17:15

2 Answers 2

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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$
    – Sasho Nikolov
    Commented Mar 3, 2017 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
    Commented Mar 3, 2017 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
    Commented Mar 3, 2017 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$
    – Sasho Nikolov
    Commented Mar 5, 2017 at 4:57

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