7
$\begingroup$

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})$?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Jun 6, 2015 at 16:15
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ran G.
    Commented Jun 6, 2015 at 16:42
  • $\begingroup$ I'd call it "linear-ish". $\endgroup$
    – Ryan Dougherty
    Commented Jun 6, 2015 at 16:49

1 Answer 1

Reset to default
1
$\begingroup$

The term I've seen in use is superlinear, as in "Are there super-linear time complexity lower bounds for any natural problem in NP?"

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.