What should I call algorithms with non-linear non-constant time?

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.

• I have seen the term “super-linear” used before, but I’m not sure if that’s the well accepted term. May 7 '19 at 3:44
• Linearithmic commonly refers to $n \log n$ time.
– ryan
May 7 '19 at 3:56
• @BryceKille "super-linear" just means "anything more than linear". May 7 '19 at 14:16
• @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. May 7 '19 at 20:10
• @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! May 9 '19 at 23:16

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"?)

• 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. May 7 '19 at 14:18
• "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. May 7 '19 at 20:14
• @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. May 9 '19 at 23:19

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

• Right. They often won't. May 14 '19 at 0:10

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.

• 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. May 7 '19 at 14:19
• 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! May 7 '19 at 21:30