23

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

4

4 Answers 4

62

"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.

4
  • 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. Jul 19, 2015 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, 2015 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, 2015 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, 2015 at 19:33
52

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".

2
  • 11
    Never even knew that existed! Jul 19, 2015 at 1:38
  • Never heard this name in my life. And I would never guess that linearithmetic is supposed to mean n log n. And my spelling checker thinks it is two words (line arithmetic).
    – gnasher729
    Apr 12, 2022 at 10:08
13

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.

4
  • 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. Jul 18, 2015 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. Jul 18, 2015 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. Jul 18, 2015 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 :-) Jul 18, 2015 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.

1
  • It's really "slightly more than linear". n / log log n would be "almost linear".
    – gnasher729
    Apr 12, 2022 at 10:11

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