1
$\begingroup$

I don't have a strong CS background so apologies if the question is trivially simple:

So I am working on an algorithm, say $A(n)$ , which runs over all integer partitions of $n$. Now the algorithm calls a sub-routine $S(\pi)$ for each of the partition $\pi$ (and does nothing else). The time-complexity of running the subroutine is $O(n^c)$ for some constant $c$.

Now the number of integer partitions is $\frac{1}{4n\sqrt 3}\exp\Big(\pi \sqrt \frac{2n}{3}\Big)$. And hence, the time complexity of my algorithm should be $O(e^{\pi\sqrt \frac{2n}{3}}n^{c'})$ or maybe just $O(e^{\pi\sqrt \frac{2n}{3}})$ or just $O(e^{\sqrt n})$ ?

Also, in my understanding I can call this SubEXP in the sense of $\textbf{III}$ category presented here.

I would basically like to understand how best to describe this complexity in an academically accurate manner. Thanks alot !

$\endgroup$
2
  • $\begingroup$ is the subroutine with running time $O(n^c)$ with respect to the original $n$ or to the size of the partition $\pi$? $\endgroup$
    – nir shahar
    Commented Jul 6, 2021 at 14:51
  • $\begingroup$ The original $n$. $\endgroup$
    – SagarM
    Commented Jul 6, 2021 at 14:52

1 Answer 1

2
$\begingroup$

Lets say there are $N(n)$ partitions. Then, for each partition you do $O(n^c)$ work (important note: make sure for all partitions this is the same $O(n^c)$. That is, for this particular $c$, for all partitions it takes $O(n^c)$!)

This means that the total work will be $O(n^c)$ times $O(N(n))$ (because you do $O(n^c)$ work for $N(n)$ iterations), hence a total of $O(N(n)\cdot n^c)$. Substitute here the number of partitions $N(n)$ and this will be the running time.

This running time is indeed considered sub-exponential in terms of category $\textbf{III}$ from the link you provided (and hence it is also $\textbf{IV},\textbf{V},\textbf{VI}$ in those terms), since the algorithm takes $$O\left(e^{c\cdot n^{\frac{1}{2}}}\right)=O\left(2^{\ln(2)\cdot c\cdot n^{\frac{1}{2}}}\right)=O\left(2^{n^\epsilon}\right)$$ for any $\epsilon>\frac{1}{2}$ of your choice. Note, that this isn't category $\textbf{II}$ as this is true only if $\frac{1}{2}<\epsilon$, rather than for all $0<\epsilon$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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