Menu
We usually have a single word 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?
590
linearithmic: adj. Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of 'linear' and 'logarithmic' in Algorithms In C by Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).
O(logn) means that the algorithm's maximum running time is proportional to the logarithm of the input size. O(n) means that the algorithm's maximum running time is proportional to the input size. basically, O(something) is an upper bound on the algorithm's number of instructions (atomic ones).
Logarithmic time complexity log(n): Represented in Big O notation as O(log n), when an algorithm has O(log n) running time, it means that as the input size grows, the number of operations grows very slowly. Example: binary search.
O(n) represents the complexity of a function that increases linearly and in direct proportion to the number of inputs. This is a good example of how Big O Notation describes the worst case scenario as the function could return the true after reading the first element or false after reading all n elements.
O(n log n) == "linearithmic" Seems to have been coined by Robert Sedgewick in the book Algorithms In C. Also called quasilinear or loglinear. However, linearithmic has the added bonus of not being an overloaded term (quasilinear is used in economics and differential equations, while loglinear is used in economics and regression analysis).
85
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
