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
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community"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.
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.
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.
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.