Asymptotic Notations - Big Oh

Big-Oh notation pronounced as big o, is the upper bound of a function is denoted as capital O.

Definition: Suppose we have two functions f(n) and g(n), then the function f(n) = O(g(n) if and only if there exists two positive constants c and k, such that f(n) <= c * g(n) for all n >= k

For example:

Suppose, if f(n) = 2 * n + 3, then

2 * n + 3 <= 5 * n for all n >= 1.

In the above equation,
c = 10, k = 1, and g(n) = n

Now we know that, n < n log(n) < n^2 < n^3 < — < 2^n < 3^n <---- n^n.
In the above comparison, n log(n), n^2, n^3, —, 2^n, 3^n, —, n^n are upper bound.

This symbolizes,

  1. f(n) = O(n) — True
  2. f(n) = O(n^2) — True
  3. f(n) = O(3^n) — True, and so on…

Finally, in Big-Oh, we take the the nearest g(n), which in this case is O(n).