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

Posted by jemfinch on Stack Overflow See other posts from Stack Overflow or by jemfinch
Published on 2010-04-14T17:05:06Z Indexed on 2010/04/14 17:13 UTC
Read the original article Hit count: 137

Filed under:
|

We usually have a single-word shorthand 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 English to refer to that complexity. Is this a gap in my knowledge, or a real gap in our English discourse on computational complexity?

© Stack Overflow or respective owner

Related posts about complexity

Related posts about algorithms