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.
Big-Omega – The Lower Bound
function f (n) belongs to big-omega of g (n) if there exist positive
suchthat for all values of
,the value of f (n) is greater than
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
n0such that for all values
,the value of f (n) is sandwiched between
c1times 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)