22

What term can I use to describe something with O(N log N) complexity?

For example:

  • O(1): Constant

  • O(log N): Logarithmic

  • O(N): Linear

  • O(N log N): ??????

  • O(N2): Quadratic

  • O(N3): Cubic

60

"N log N" is as good as you're going to get, and should be well understood by professional programmers. You can't expect there to be a single word to describe every complexity class that exists.

  • 6
    “can't expect there to be a single word to describe every complexity class” – certainly not. But 𝓞 (n ⋅ log n) is such an important class that it does deserve a name of its own, IMO; and as said by Steve Jessop, linearithmic is pretty common already. – leftaroundabout Jul 19 '15 at 13:03
  • @leftaroundabout It is indeed common enough that you could argue, that it does deserve a name. But "n log n" is short enough to pronounce (only three syllables) that it works fine as a name. For comparison "Logarithmic" is four syllables. It's more interesting when you get to external algorithms where most of the "n log n" algorithms get complexity $N log_B (N/B)$, that would certainly be a complexity class worthy of a shorter name. – kasperd Jul 19 '15 at 14:18
  • 10
    As a computer science master's degree student, I have heard "enn log enn" throughout my college studies. I have never heard "linearithmic" and would not understand what it meant at first. – Kevin Jul 19 '15 at 23:41
  • @Kevin: Logarithmic is four syllables, but "log-enn" is only two. Likewise, O(N^2) is "enn-squared", not "quadratic". I suppose "cubic" has fewer phonemes than "enn-cubed", but I think the latter term would still be more common. – supercat Jul 26 '15 at 19:33
51

There is a jargon term linearithmic meaning exactly this.

I don't believe that it's universally understood by all programmers, so if you're not careful then it will obscure more than it informs. Personally I don't normally use it, and if I did then I'd probably define it on first use, for example "this article considers linearithmic (O(N log N)) algorithms".

  • 11
    Never even knew that existed! – David Grinberg Jul 19 '15 at 1:38
12

It is sometimes called "loglinear", although that word actually means something different. I would just stick with "N log N", though, as @Philip's answer suggests.

  • 1
    What's the alternative meaning for log-linear? If I wanted a name other than 'N log N', log-linear is the term I'd use. – Jonathan Leffler Jul 18 '15 at 13:10
  • 2
    @JonathanLeffler: I assume en.wikipedia.org/wiki/Log-linear_analysis sometimes spelled without the hyphen. Of course with proper namespacing you could happily use the same word for a complexity class. – Steve Jessop Jul 18 '15 at 13:21
  • @SteveJessop: That's certainly what came up via a Google search. I'm not sure whether I'm willing to accept the Google/Wikipedia combo as authoritative, though I have zero doubt that log-linear analysis is as described. – Jonathan Leffler Jul 18 '15 at 13:28
  • 1
    @JonathanLeffler: could also mean what I'd call a lin-log or log-lin plot (or, because I'm lazy, actually I'd often call them a log plot as distinct from a log-log one). We might perhaps ask, which alternative meaning this answer has in mind :-) – Steve Jessop Jul 18 '15 at 13:34
2

Because the factor log n grows slowly, a qualitative description for O(n log n) would be "almost linear". Depending on your audience the class of O(n log n) algorithms might be well known, as for example this is the case with fast sorting on n items by comparisons.

protected by gnat Aug 1 '15 at 19:23

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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