Big O Notation - Properties

Properties

If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example

In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial. O(nc) and O(cn) are very different. If c is greater than one, then the latter grows much faster. A function that grows faster than nc for any c is called superpolynomial. One that grows more slowly than any exponential function of the form is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization. O(log n) is exactly the same as O(log(nc)). The logarithms differ only by a constant factor (since ) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. Exponentials with different bases, on the other hand, are not of the same order. For example, and are not of the same order. Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of n2, replacing n by cn means the algorithm runs in the order of, and the big O notation ignores the constant . This can be written as . If, however, an algorithm runs in the order of, replacing n with cn gives . This is not equivalent to in general. Changing of variable may affect the order of the resulting algorithm. For example, if an algorithm's running time is O(n) when measured in terms of the number n of digits of an input number x, then its running time is O(log x) when measured as a function of the input number x itself, because n = Θ(log x).