## Asymptotic Notations – II

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 ofg (n)if there exist positiveconstants `c`

and `n0`

such that for all valuesof `n`

greater than `n0`

, the value off (n)is greaterthan `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 ofg (n)if there exist positiveconstants `c1`

, `c2`

, and`n0`

such that for all valuesof `n`

greater than `n0`

, the value off (n)is sandwiched between`c1`

timesg (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

```
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)`

## Leave a Reply