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 Answers
"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.
answered Jul 18, 2015 at 7:08
-
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.– kasperdJul 19, 2015 at 14:18
-
10As 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.– KevinJul 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.– supercatJul 26, 2015 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".
-
11
-
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). Apr 12, 2022 at 10:08
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.
answered Jul 18, 2015 at 8:44
-
1What'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
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.
-
It's really "slightly more than linear". n / log log n would be "almost linear". Apr 12, 2022 at 10:11
O(n · f(n))wheref(n) << n. But this matches also things likeO(n · log log n)andO(n α(n))whereα(n)is the inverse of the Ackermann function.