# When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?

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(N3): Cubic

• 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. Jul 18 '15 at 17:44
• en.wikipedia.org/wiki/…
– Ry-
Jul 18 '15 at 19:44
• "Oh enn log enn" is probably good enough. Jul 19 '15 at 2:12
• Cross-site duplicate here: What is the name the class of functions described by O(n log n)? Jun 6 '17 at 6:03

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

• “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 '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. Jul 19 '15 at 14:18
• 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. 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. Jul 26 '15 at 19:33

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

• Never even knew that existed! Jul 19 '15 at 1:38

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.

• 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 '15 at 13:10
• @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 '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. Jul 18 '15 at 13:28
• @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 '15 at 13:34

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.