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

Question

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(N²): Quadratic

• O(N³): Cubic

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.