BIG-O, Omega and Theta notations in algorithms

Having the expression for the best, average and worst cases, for all the three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds we need some kind of syntax and that is the subject of the following discussion about different notations. Let us assume that the given algorithm is represented in the form of function f(n).

Big-O Notation:

Big-O Notation gives the tight upper bound of the given function. Generally, it is represented as f(n)=O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n).

For example, f(n) = n4 + 100n2 + 10n + 50 is the given algorithm, then n4 is g(n). That means g(n) gives the maximum rate of growth for f(n) at larger values of n.

Let us see the O-notation with little more details. O- notation defined as O(g(n))={f(n): there exists positive constants c and n0}. g(n) is an asymptotic tight upper bound for f(n). Our objective is to give smallest rate of growth g(n) which is greater than or equals to given algorithm rate of growth f(n).

Generally we discard lower values of n. That means the rate of growth at lower values of n is not important. In the below figure, n0 is the point from which we need to consider the rate of growth for a given algorithm. Below n0 the rate of growth could be different.

Big-O Visualization:
O(g(n)) is the set of functions with smaller or same order of growth as g(n). For example, O(n2) includes O(1), O(nlogn) etc…

Note: Analyze the algorithms at large values of n only. What is that mean is, below n0 we do not care for rate of growth.

No Uniqueness:
There are no unique set of values for n0 and c in providing asymptotic bounds. Let us consider, 100n + 5 = O(n). For this function there are multiple n0 and c values possible.

Solution1: 100n + 5 ≤ 100n + n = 101n ≤ 101n, for all n ≥ 5, n0=5 and c=101 is a solution.
Solution2: 100n + 5 ≤ 100n + 5n = 105n ≤ 105n, for all n ≥ 1, n0=1 and c=105 is also a solution.

Omega-Ω Notation:

Similar to O discussion, this notation gives the tighter lower bound of the given algorithm and we represent it as f(n) = Ω(g(n)). That means, at larger values of n, the lower bound of f(n) is g(n). For example, if f(n) = 100n2 + 10n + 50, g(n) is Ω(n2).

The Ω notation can be defined as Ω(g(n))={f(n): there exists positive constants c and n0such that 0≤cg(n)≤f(n) for all n≥n0}. g(n) is an asymptotic tight lower bound for f(n). Our objective is to give largest rate of growth g(n) which is less than or equal to given algorithms rate of growth f(n).

Theta-Θ Notation:

This notation will decides whether upper and lower bounds of a given algorithm are same. The average running time of algorithm is always between lower bound and upper bound. If the upper bound(O) and the lower bound(Θ) give the small result then Θ notation will have the same rate of growth. As an example, let us assume that f(n) = 10n + n is the expression.

Then it’s tight upper bound g(n) is O(n). The rate of growth in best case is g(n)=O(n).

In this case, rate of growths in the best case and worst case are same. As a result, the average case will also be same. For a given algorithm, if the rate of growths for O and Ω are not same then the rate of growth Θ case may not be same. In this case, we need to consider all possible time complexities and take average of those.

Now, consider the definition of Θ notation. It is defined as Θ(g(n)) = {f(n): there exist positive constants c1,c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥n0}. g(n)is an asymptotic tight bound for f(n). Θ(g(n)) is the set of functions with the same order of growth as g(n).