# 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

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

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

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. – Jonathan Leffler 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. – 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
• @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

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.