Does this Qualify as Sub-Exponential?

Question

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 !

Answer 1

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