Is there a shorthand term for O(n log n)?
- by jemfinch
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?
