Asymptotic notation
Let us describe a few functions in terms of above asymptotic notation.
Example: f(n) = 3n^{3} + 2n^{2} + 4n + 3
= 3n^{3} + 2n^{2} + O (n), as 4n + 3 is of O (n)
= 3n^{3}+ O (n^{2}), as 2n^{2} + O (n) is O (n^{2})
= O (n^{3})
Example: f(n) = n² + 3n + 4 is O(n²), since n² + 3n + 4 < 2n² for all n > 10.
Through definition of big-O, 3n + 4 is also O(n²), too, although as a convention, we employ the tighter bound to the function, i.e., O(n).
Here are some rules regarding big-O notation:
1. f(n) = O(f(n)) for any function f. In other terms, every function is bounded by itself.
2. a_{k}n^{k} + a_{k-1 }n ^{k-1} + • • • + a_{1}n + a_{0} = O(nk) for every k ≥ 0 & for all a_{0}, a_{1}, . . . , a_{k} ∈ R.
In other terms, every polynomial of degree k may be bounded through the function n_{k}. Smaller order terms can be avoided in big-O notation.
3. Basis of Logarithm can be avoided in big-O notation that means log_{a}n = O(log_{b} n) for any bases a, b. Generally we write O(log n) to specify a logarithm n to any base.
4. Any logarithmic function may be bounded through a polynomial that means. log_{b} n = O(n^{c}) for any b (base of logarithm) & any positive exponent c > 0.
5. Any polynomial function may be limited by an exponential function i.e. n^{k} = O (b^{n}.).
6.Any exponential function may be limited by the factorial function. For instance, a^{n} = O(n!) for any base a.