* A specialized notation is used to compare the relative complexity of an algorithm. Using this measure, we can categorize quickly the relative runtime of an algorithm as well as perform qualitative comparisons between algorithms. This measure is called Big-O notation.
* The Big-O notation expresses the runtime of an algorithm as a function of a given input of size n. For example, if the runtime grows linearly with the number of elements (doubling the input doubles the runtime) the complexity is O(n). If the runtime is independent of the input, the complexity is O(1).
* The following Table lists typical values of complexity and their Big-O notation.
Constant : O(1) : The runtime is independent of the number of elements.
Logarithmic : O(log(n)) : The runtime grows logarithmically with respect to the number of elements.
Linear : O(n) : The runtime grows linearly (with the same factor) as the number of elements grows.
n-log-n : O(n *log(n)) : The runtime grows as a product of linear and logarithmic complexity.
Quadratic : O(n2) : The runtime grows quadratically with respect to the number of elements.
* It is only a rule of thumb; the algorithm with optimal complexity is not necessarily the best one.
* Some complexity definitions in the C++ reference manual are specified as amortized. This means that the operations in the long term behave as described.
* However, a single operation may take longer than specified. For example, if you append elements to a dynamic array, the runtime depends on whether the array has enough memory for one more element.
* If there is enough memory, the complexity is constant because inserting a new last element always takes the same time.
* But, if there is not enough memory, the complexity is linear. This is because, depending on the actual number of elements, you have to allocate new memory and copy all elements.
* Reallocations are rather rare, so any sufficiently long sequence of that operation behaves as if each operation has constant complexity. Thus, the complexity of the insertion is "amortized" constant time.
