<p>Have you seen the concept of PTAS (Polynomial-time approximation scheme)? I think is kind of what you are looking for. See <a href="https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme" rel="nofollow noreferrer">link</a></p>

CC BY-SA 4.0
2023-03-28T11:51:40.227Z
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$.
Thomas S
CC BY-SA 4.0
2023-03-28T08:18:53.147Z
2023-03-28T08:18:53.147Z
Wilmer Bandres Hernández
<p>Assume for some algorithmic problem it holds that, for each <span class="math-container">$\epsilon&gt;0$</span>, there is some algorithm that needs space at most <span class="math-container">$O(n^\epsilon)$</span>.</p>
<p>Is there an established name for this kind of bound?</p>
<p>I'd like to stress that it is not the same as having an algorithm with space complexity <span class="math-container">$n^{o(1)}$</span>, since in the above, the algorithm can be different, for each <span class="math-container">$\epsilon$</span>.</p>
<p>I am actually not interested in such a bound with respect to space, but with respect to work for parallel algorithms.</p>

<upper-bounds>
Is there an established name for this kind of upper bound?
Thomas S
# Is there an established name for this kind of upper bound?

(Asked by: username_0 on 2023-03-27)

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.

**Tags:** upper-bounds

---

## 1 answers

### Answer by username_1 on 2023-03-28. Score: -2

Have you seen the concept of PTAS (Polynomial-time approximation scheme)? I think is kind of what you are looking for. See [link](https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)

> **Comments:**
> **username_0**: 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$.  

---

