patternCritical
What is the name the class of functions described by O(n log n)?
Viewed 0 times
thewhatlogdescribednamefunctionsclass
Problem
In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):
O(1) is "Constant"
O(log n) is "Logarithmic"
O(n) is "Linear"
O(n^2) is "Quadratic"
O(n * log n) is ???
Is it just "n log n" or does it have a special name like the above?
O(1) is "Constant"
O(log n) is "Logarithmic"
O(n) is "Linear"
O(n^2) is "Quadratic"
O(n * log n) is ???
Is it just "n log n" or does it have a special name like the above?
Solution
It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.
Context
StackExchange Computer Science Q#76317, answer score: 54
Revisions (0)
No revisions yet.