What term can I use to describe something with O(N log N) complexity?
O(log N): Logarithmic
O(N log N): ??????
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.
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?