39
$\begingroup$

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):

O(1) is "Constant"

O(log n) is "Logarithmic"

O(n) is "Linear"

O(n^2) is "Quadratic"

O(n * log n) is ???

Is it just "n log n" or does it have a special name like the above?

|cite|improve this question
$\endgroup$
52
$\begingroup$

It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles♦ Jun 7 '17 at 0:03
17
$\begingroup$

linearithmic: adj.

Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of ‘linear’ and ‘logarithmic’ in Algorithms In C by Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

http://catb.org/jargon/html/L/linearithmic.html

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why am I not surprised that it comes from Sedge... :) $\endgroup$ – TextGeek Jun 5 '17 at 15:41
11
$\begingroup$

I've always heard O(n log n) described as "log-linear" which seems about right to me.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ That said, a reference or two would be nice. $\endgroup$ – Raphael♦ Jun 5 '17 at 20:26
7
$\begingroup$

This was too long for a comment, so I wrote an answer. I did not add this to my first answer because a lot of people already upvoted my first vanswer and I am not sure they agree with this answer, too.

  • I don't think that linearithmic is a well established term as stated in a comment to the accepted answer. I googled some rather young articles using this term, a CS course and another book by Sedgewick that uses this term and a lot of online dictionaries.
  • The term quasilinear I found in two articles:

    Satisfiability Is Quasilinear Complete in NQL
    C. P. Schnorr
    Journal of the Association for Computing Machinery,
    Vol 25. No 1, January 1978, pp 136-1,15

and in an article cited in the Wikipedia that deals with this Schorr's article. Schnorr introduces the complexity classes quasilinear (QL) and nondeterministic quasilinear (NQL).
Quasilinear seems to be used in the theory of partial differential equations, too.

All in all it seems that one or more Wikipedians wanted to supply names for this function that does not have a widely accepted name. But even now it seems to me that none of the names is widely accepted (besides that I think this is a kind of manipulation that Wikipedia should not do). I think one has to be cautious if one uses Wikipedia for terminology questions. And for this function it is not a sufficient source. I think the only widely accepted name for this function is n log n.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ While the legitimacy of linearithmic and loglinear might be debatable, I believe that quasi-linear is a well-established term. It seems to be widely used in research papers. $\endgroup$ – Roukah Jun 6 '17 at 13:10
  • $\begingroup$ @Roukah yes, but it does not mean quite the same thing; quasilinear is more general. — I don't see what's wrong with Wikipedia using a name that is unambiguous, appears to have no better alternative, and is used in a reasonably renowned source, even if it hasn't much spread. In fact I'd say the fact that it hasn't spread despite being an extremely common complexity class suggests it's about time people started using it more! $\endgroup$ – leftaroundabout Jun 6 '17 at 14:12
  • $\begingroup$ +1 "only widely accepted name for this function is n log n" - All the other answers are entertaining and edifying, but I think you may be right. I've been practicing saying "linearithmic" for a couple days now and it still doesn't roll off the tongue. "En log en" is easy to say, easy to remember, and instantly understood by everyone familiar with Big O. I'll think about it a bit, but I might have to move my acceptance to this answer. $\endgroup$ – GlenPeterson Jun 6 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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