Assume for some algorithmic problem it holds that, for each $\epsilon>0$, there is some algorithm that needs space at most $O(n^\epsilon)$.

Is there an established name for this kind of bound?

I'd like to stress that it is not the same as having an algorithm with space complexity $n^{o(1)}$, since in the above, the algorithm can be different, for each $\epsilon$.

I am actually not interested in such a bound with respect to space, but with respect to work for parallel algorithms.


1 Answer 1


Have you seen the concept of PTAS (Polynomial-time approximation scheme)? I think is kind of what you are looking for. See link

  • 1
    $\begingroup$ Thank you. I know PTAS and I can see the analogy you see (for every $\epsilon$ there is an algorithm...). But I am specifically interested in settings, where the bound is of the form $n^\epsilon$. $\endgroup$
    – Thomas S
    Commented Mar 28, 2023 at 11:51

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.