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

Thomas Owens
  • 79,623
  • 18
  • 192
  • 283
matiascelasco
  • 385
  • 2
  • 10
  • 5
    I often here the broad term "quasi-linear" to mean `O(n · f(n))` where `f(n) << n`. But this matches also things like `O(n · log log n)` and `O(n α(n))` where `α(n)` is the inverse of the Ackermann function. – Bakuriu Jul 18 '15 at 17:44
  • https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities – Ry- Jul 18 '15 at 19:44
  • 36
    "Oh enn log enn" is probably good enough. – user253751 Jul 19 '15 at 02:12
  • Cross-site duplicate here: [What is the name the class of functions described by O(n log n)?](https://cs.stackexchange.com/questions/76317/what-is-the-name-the-class-of-functions-described-by-on-log-n) – martin Jun 06 '17 at 06:03

4 Answers4

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.

Philip Kendall
  • 22,899
  • 9
  • 58
  • 61
  • 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
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".

Steve Jessop
  • 5,051
  • 20
  • 23
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.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
  • 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 https://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.

hardmath
  • 826
  • 1
  • 8
  • 12