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 of g (n) if there exist positive
constants c
and n0
such that for all valuesof n
greater than n0
, the value of f (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 of g (n) if there exist positive
constants c1
, c2
, andn0
such that for all valuesof n
greater than n0
, the value of f (n) is sandwiched betweenc1
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
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