In this chapter we shall learn about below topics:
6.1 Big Omega
6.2 Example
6.3 Big Theta Ø
In the previous chapter we learnt about Big O notation, that defines tight upper bound. In this chapter we shall see about Big Omega and Big Theta notation.
6.1 Big Omega Ω:
This notation is used to represent tight lower bound. Big omega can be defined as:
For a function f(n) is equal to Ω(g(n)) if there exist a constant C and n0 such that f(n) is always greater than C(g(n)). i.e. f(n) > C(g(n)) or C(g(n)) < f(n).
6.2 Example:
f(n) = 2n + 3 and g(n) = n
Then we need to reduce f(n) to g(n).
Now, when C = 1 we will be able to satisfy the condition.
i.e (2n+3) > (1*n) for all n >=1.
Hence we can say that f(n) is equal to Ω(n).
Hence from the above example we can come to below image.
6.3 Big Theta Ø
Big theta is used to get the average case for a function. It can be defined as:
For a function f(n) is equal to Ø(n) if a function f(n) is greater than C1 g(n) and is less than C2g(n) for all n>= 0. It means that the function f(n) will always be in-between C1*g(n) and C2*g(n). It can be shown in formula as : C1 g(n) <= f(n) <= C2 g(n).
In other words, if you want to prove big theta, then find out the big O and big Omega separately and you will be able to prove big theta.
Let us take an example and understand Big Theta:
Given f(n) = 5n^2 + 2n + 1
g(n)= n^2
we need to prove C1 g(n) <= f(n) <= C2 g(n)
c1 = 5 and c2 = 8 and n1 = 1
5 * 1 <= (5 (1^2) + 2*1 + 1 <= 8 * 1
Thus proving f(n) = Ø(n^2).
AJ’s guide for DS and Algorithms.Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.
