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

$\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 ♦
    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.
    Jun 6, 2015 at 16:42
  • $\begingroup$ I'd call it "linear-ish". $\endgroup$
    – Ryan Dougherty
    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?"

$\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
    Jun 7, 2015 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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