# Does this Qualify as Sub-Exponential?

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 !

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

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