Go backward to 6.5 Special Functions
Go up to 6 More on Functions
S = On(T)is a proposition with bound variable n which is read as "S is big O of T" or "T asymptotically dominates (dominiert asymptotisch) S".
Its meaning is equivalent to the proposition
exists c in R, m in N: forall n >= m: |S| <= c*|T|.
Usually the subscript n is dropped and the bound variable has to be deduced from the context.
The proposition S = On(T) states that, from a certain point m on and scaled by some factor c, the absolute value of T is at least as large as the absolute value of S. The function [T]n thus grows at least as fast as [S]n.
For instance, instead of saying that the execution time T of some algorithm A in dependence on input size n is TA(n) = 7n2+3n+19, we may say
TA(n) = O(n2),i.e., that the execution time is asymptotically dominated by the square function and ignore all constant factors and minor terms.
Sometimes, we also see propositions like
S0 = S1 + O(T)which is to be understood as S0 - S1 = O(T). For instance, by saying
f(n) = 5n3 + 2n2 + O(n)we state that f(n) differs from 5n3 + 2n2 not more than by some linear factor.
Let c := 110 and m:=1 and take arbitrary n >= m. We have to show
|10n+100| <= c*|n|.
|10*n+100| = 10*n+100 <= 110n = 110|n| = c|n|.
We suppose n2 = O(n) and show a contradiction. By the assumption, we have some c in R and m in N with
forall n >= m: |n2| <= c|n|.
If c < 0, let k:=max(1, m); then we have k >= m but
and thus a contradiction.
|k2| > 0 > c|k|
If c >= 0, let k := max(m, ceiling(c+2)). Then we have k >= m but
and thus a contradiction.
|k2| = k2 >= ceiling(c+2)2 >= (c+2)2 = c2 +4c + 4 > c2 +3c = c(c+3) >= cceiling(c+2) >= ck = c|k|
We assume not n2 = O(2n) and show a contradiction. By assumption, we have ~exists c in R, m in N: forall n >= m: |n2| <= c|2n|, i.e.,
forall c in R, m in N: ~forall n >= m: |n2| <= c|2n|.
by induction on n and thus have a contradiction.
forall n >= 0: n2 <= 2*2n
If n=0, we have n2 = 0 < 2 = 2*20 = 2*2n.
We assume n >= 1 => n2 <= 2*2n and show
Assume n+1 >= 1. We show
n+1 >= 1 => (n+1)2 <= 2*2n+1.
(n+1)2 <= 2*2n+1.
If n < 1, then n = 0 and
(n+1)2 = (0+1)2 = 1 < 4 = 2*20+1 = 2*2n+1.
If n >= 1, then, by the induction hypothesis, n2 <= 2*2n. We then have
(*) The fact 2n <= 2n has to be shown in a separate proof.
(n+1)2 = n2 + 2n + 1 <= n2 + 2n + 2n (*) <= 2*2n + 2n + 2n = 2n+1 + 2n+1 = 2(2n+1).
It is easy to derive a number of laws for the manipulation of O terms.
S -> On(S), c+On(S) -> On(S), c*On(S) -> On(S), On(S) + On(S) -> On(S), On(On(S)) -> On(S), On(S) + On(T) -> On(|S|+|T|), On(S) * On(T) -> On(S * T), On(S) * On(T) -> S*On(T), On(Sc) -> On(Sd).
Thus we can replace a statement
f(n) = 2n2 - 7n + 5via the transformations
by the statement
2n2 - 7n + 5 -> 2*O(n2) - 7*O(n) + 5*O(1) -> O(n2) + O(n) + O(1) -> O(n2) + O(n2) + O(n2) -> O(n2)
f(n) = O(n2).
This example illustrates that the asymptotic behavior of a polynomial sequence is asymptotically dominated by the polynomial term with the highest degree.
forall n in N, a: Nn -> R: (sum0 <= i <= n axi) = On(xn).
For comparing the asymptotic behavior of classes of real functions, the following notation comes handy.
S < n Tis a proposition with bound variable n which is read as "S is strictly dominated by T" and that is equivalent to
S = On(T) /\ T != On(S).
We then have the following chain of function classes:
1 < n loga(n) < n n < n nloga(n) < n nk< n cn < n n!
The corresponding function graphs are visualized below.
To get some "feeling" for the growth rate of these functions, assume that we have a machine that performs 106 operations per second. We are given six algorithms whose number of execution steps in dependence of the problem size n is determined by one of the six functions denoted above. Then the maximum size of a problem that can be solved in a fixed amount of time is
Execution Steps 1 second 1 minute 1 hour log2(n) 2106 26*107 236*108 n 106 6*107 3.6*109 nlog2(n) 62746 2.8*106 1.3*108 n2 1000 7746 60000 2n 23 26 32 n! 9 11 12
A sorting algorithm that takes, for some logarithmic base, O(nlog(n)) steps (such as Quicksort) is therefore much better than an n2 algorithm (such as Insertion Sort); the difference in computation time may be not significant for small inputs but the larger the inputs become, the more the asymptotic complexity distinguishes the algorithms.
Also we can see that, for algorithms with exponential (or higher) complexity, the only problems of extremely small size can be solved. Furthermore, it does not help much to allow say 1000 times more execution time (or use a 1000 times faster machine or apply a parallel computer with 1000 processors); the manageable problem size does not increase significantly. Problems for which only exponential time algorithms exist are therefore called intractable (ungefügig). For instance, to find out whether a propositional formula with n variables is a tautology is such an intractable problem.