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.

$\endgroup$
  • $\begingroup$ I have seen the term “super-linear” used before, but I’m not sure if that’s the well accepted term. $\endgroup$ – Bryce Kille May 7 at 3:44
  • 1
    $\begingroup$ Linearithmic commonly refers to $n \log n$ time. $\endgroup$ – ryan May 7 at 3:56
  • $\begingroup$ @BryceKille "super-linear" just means "anything more than linear". $\endgroup$ – David Richerby May 7 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 May 7 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 May 9 at 23:16
2
$\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"?)

$\endgroup$
  • $\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 May 7 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 May 7 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 May 9 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.

$\endgroup$
  • 1
    $\begingroup$ Right. They often won't. $\endgroup$ – ameerosein May 14 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.

$\endgroup$
  • $\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 May 7 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 May 7 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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