In this post, we will see the remaining two asymptotic notations. The algorithm we were discussing was the linear search. We had calculated the estimated time complexity as 2n + 3.

To read the previous post, click here.

Big-Omega – The Lower Bound

function f (n) belongs to big-omega of g (n) if there exist positive constants c and n0 such that for all values of n greater than n0, the value of f (n) is greater than c times g (n).

Big omega is the simple one. We have to find the constant and the minimum value of n to satisfy this condition. Let’s see how we can do that.

The condition that needs to be satisfied is as follows,

2n + 3 >= c.g (n)

It is quite clear, due to the constant value 3 on the LHS, that if we put 'n' on the RHS, this equation will become valid.

2n + 3 >= 1.n

This equation will hold true for all positive values of 'n' when c is 1.

Therefore we can say,

f (n) >= n, for n >= 1
or,
f (n) = Ω (n)

Theta – The Average Bound

function f (n) belongs to theta of g (n) if there exist positive constants c1, c2, and n0 such that for all values of n greater than n0, the value of f (n) is sandwiched between c1 times g (n) and c2 times g(n).

Let’s quickly calculate the required g (n) function. We have already found this in the previous two examples, so I’ll keep it short.

The condition that needs to be satisfied is as follows,

c1.g(n) <= f (n) <= c2.g(n)

or,

1.n <= 2n + 3 <= 5.n

This gives us,

c1 = 1,
c2 = 5,
g (n) = n,
n0 = 1

Thus we can write,

n <= f (n) <= n
or,
f (n) = Θ (n)

In all three scenarios, we found the g (n) to be ‘n’. So, you must be wondering, what’s the difference between big-oh, big-omega, and theta function.

In one of the previous post of this series, we came across different types of time functions and their order, starting from the lowest to highest.

1 < log (n) < sqrt (n) < n < n^2 < n^3 … 2^n < 2^n … < n^n

Based on this functions’ degree level, we can say, Big-Oh can be any of the functions bigger than ‘n’. That is, all the following is true but we always consider the closest one to be the one.

f (n) = O (n^2)
f (n) = O (n^3)
.
.
.
f (n) = O (n^n)

Similarly, big-omega can be any of the functions smaller than ‘n’.

f (n) = Ω (sqrt (n))
f (n) = Ω (log n)
f (n) = Ω (1)

But, the theta function can only be the one that we found out.

f (n) = Θ (n)