# What is the name for the complexity class $O(n^{1+\epsilon})$

Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive constant. I want to know the terminology for describing this complexity class.

For example, I would call a $\Theta(n)$ algorithm "linear". I would call a $\Theta(n^2)$ algorithms "quadratic". I would call a $\Theta(n \cdot log^c(n))$ algorithm "nearly linear". (Note that nearly linear is better than $O(n^{1+\epsilon})$.)

What do I call algorithms that are in $O(n^{1+\epsilon})$?

• Note that $\Theta(n \log n)$ is also called linearithmic. While I don't know about other $c$ (polylinearithmic?), that might free up "nearly" or "almost" for you. – Raphael Jun 6 '15 at 16:15
• I'm not sure there is an agreed term, but if you use either sub-quadratic, almost linear or even quasi-linear (which is sometimes used for $O(n\log n)$ as well), yet clearly define that you use this term for $O(n^{1+\epsilon})$, it will be just fine. – Ran G. Jun 6 '15 at 16:42
• I'd call it "linear-ish". – Ryan Jun 6 '15 at 16:49

• I think super-linear in that context means $\omega(n)$, as opposed to $\Theta(n^{1+\epsilon})$ or $O(n^{1+\epsilon})$. – Craig Gidney Jun 7 '15 at 1:15