Is there a shorthand term for O(n log n)?

We usually have a single word for most complexities we encounter in algorithmic analysis:

• O(1) == "constant"
• O(log n) == "logarithmic"
• O(n) == "linear"
• O(n^2) == "quadratic"
• O(n^3) == "cubic"
• O(2^n) == "exponential"

We encounter algorithms with O(n log n) complexity with some regularity (think of all the algorithms dominated by sort complexity) but as far as I know, there's no single word we can use in Engli开发者_如何学Pythonsh to refer to that complexity. Is this a gap in my knowledge, or a real gap in our English discourse on computational complexity?

• O(n log n) == "linearithmic"

Seems to have been coined by Robert Sedgewick in the book Algorithms In C. Also called quasilinear or loglinear. However, linearithmic has the added bonus of not being an overloaded term (quasilinear is used in economics and differential equations, while loglinear is used in economics and regression analysis).

"en log en" has fewer syllables than "exponential" or "logarithmic". I think most people just say that.

According to Wikipedia you can call it linearithmic, loglinear, or quasilinear.

O(2^n) == "O Scary"

I don't believe there is such a term.

More relevant, though, is this thought: Why do you refer to exponential (11 characters) as a "shorthand" for O(2^n) (6 characters)?

Personally, I'm quite happy to say "this algorithm runs in en log en time". It's all most people need to hear.

No there's no single word equivalent for O(nlogn). You just have to spend the extra time saying the whole thing (Note: same number of syllables as "exponential")