1
$\begingroup$

I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g polynomial-time) and I want to refer to them all in one term. Is there any common term to use in such a situation?

linearithmic refers to O(NLOGN) algorithms and it's narrower than what I'm looking for. I don't think of non-linear as a good term to use here. If it is, then correct me please.

my sentence:

In such a setting, state-of-the-art community-detection algorithms does not scale well. To reduce the running time of these XYZ algorithms, each sub-graph is partitioned into chunks.

I want to change `XYZ' in the above, to what I am asking for.

Improve this question
$\endgroup$
9
  • $\begingroup$ I have seen the term “super-linear” used before, but I’m not sure if that’s the well accepted term. $\endgroup$
    – Throckmorton
    Commented May 7, 2019 at 3:44
  • 1
    $\begingroup$ Linearithmic commonly refers to $n \log n$ time. $\endgroup$
    – ryan
    Commented May 7, 2019 at 3:56
  • $\begingroup$ @BryceKille "super-linear" just means "anything more than linear". $\endgroup$
    – David Richerby
    Commented May 7, 2019 at 14:16
  • $\begingroup$ @David Richerby Could you please clarify this being a duplicate? From the OP's last sentence I would say it is quite clear "linearithmic" is a much narrower term than what they are looking for. $\endgroup$
    – dkaeae
    Commented May 7, 2019 at 20:10
  • 1
    $\begingroup$ @DavidRicherby If you cant think of any, then you can add an answer and say there is not term describing it. That does not mean it's a duplicated question! $\endgroup$
    – ameerosein
    Commented May 9, 2019 at 23:16

3 Answers 3

Reset to default
4
$\begingroup$

As mentioned by Bryce Kille in the comments, superlinear is what you are looking for. From Wiktionary:

  1. (mathematics) Describing a function that eventually grows faster than any linear one

(By the way, the first phrase in your question strikes me as rather odd: "[...] I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity $O(N \log N)$." Do you simply mean "linear" instead of "polynomial-time"?)

Improve this answer
$\endgroup$
3
  • $\begingroup$ OK, but "superlinear", as you say, just means "anything bigger than linear". The function $2^{2^{2^n}}$ is superlinear, so saying that your algorithm has "superlinear" running time gives very little information, and is usually a negative statement. "Subquadratic" is probably more appropriate, since it gives an upper bound. $\endgroup$
    – David Richerby
    Commented May 7, 2019 at 14:18
  • $\begingroup$ "Subquadratic" misses the point because the OP asks for "faster than linear". If polynomial-time is not clear from the context, it can be mentioned explicitly, as Peter Taylor writes in the other answer. $\endgroup$
    – dkaeae
    Commented May 7, 2019 at 20:14
  • $\begingroup$ @DavidRicherby as my example says, I am not trying to provide and upper bound but I am trying to say that all the available algorithms out there are more complex and takes longer theoretically, that is to say a lower bound. Maybe my question is not clear enough so I appreciate if you edit it if you think you can make it more clear. $\endgroup$
    – ameerosein
    Commented May 9, 2019 at 23:19
1
$\begingroup$

On top of the other answers, you can also say $\omega(n)$ and people should know what you mean, but often won't.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Right. They often won't. $\endgroup$
    – ameerosein
    Commented May 14, 2019 at 0:10
0
$\begingroup$

I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity O(NlogN). Is there any common term to use in such a situation?

Yes: polynomial. Note that $O(N \lg N) \subset O(N^2)$.

I am trying to mention that these algorithms' running time grow faster than linear.

That makes them superlinear. If you want to be explicit about the fact that you're talking about the intersection you could say superlinear polynomial.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Be careful. Although an algorithm that runs in time $\Theta(n\log n)$ is in polynomial time, the function $n\log n$ is not itself a polynomial and shouldn't be described as one. $\endgroup$
    – David Richerby
    Commented May 7, 2019 at 14:19
  • $\begingroup$ Thanks for answering, but I don't think so... as @DavidRicherby mentioned, theyr shouldn't be described this way. This way you can any linear-time algorithm exponential... but you're not conveying information! $\endgroup$
    – ameerosein
    Commented May 7, 2019 at 21:30

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.