Asymptotic notation

Let us describe a few functions in terms of above asymptotic notation.

Example: f(n) = 3n³ + 2n² + 4n + 3

= 3n³ + 2n² + O (n), as 4n + 3 is of O (n)

= 3n³+ O (n²), as 2n² + O (n)   is O (n²)

= O (n³)

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_kn^k + a_k-1 n ^k-1 + • • • + a₁n + a₀ = O(nk) for every k ≥ 0 & for all a₀, a₁, . . . , 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_an = 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ⁿ.).

6.Any exponential function may be limited by the factorial function. For instance, aⁿ = O(n!) for any base a.