Big Omega Notation: Theory & Calculation

Before reading this article I recommend you to read following articles: 

app Big-Oh: In layman's terms and Big-Oh: Theory and Calculation.

Big-Omega notation (Ω)

We use Big-Omega (Ω) when we want to say that the algorithm takes at least this much amount of time, i.e.,

1. Its used to express the lower bound of an algorithm's running time. 
2. It measures the best case time complexity i.e.,
3. The best amount of time an algorithm can possibly take to complete.

Let,
           n   → size of program's input.
       T(n) → function that we are bounding.

Definition:

Ω(f(n)) ≥ { T(n) : there exists d > 0 and N such that T(n) ≤ d.f(n) for all n > N } 

Fig. 1: Time complexity : Graph to explain Big-Omega Notation

Formally, Ω(f(n)) is the  set of all functions that satisfy, there exist +ve constants d and N>0 such that, for all n≥N,

T(n)≥d.f(n)
T(n) = Ω(f(n))

Big-Omega (lower bound) is another commonly used asymptotic notation which is an exact opposite of Big-Oh notation (Upper bound).

Note:  Big-Omega(Ω) is the reverse of Big-Oh (O),
⇒ If T(n) ∈ O(f(n)) it also implies that,
⇒    f(n)  ∈ Ω(T(n)) 

So we can say, 
2n ∈ Ω(n) because n ∈ O(2n)
n² ∈ Ω(n) because n ∈ O(n²)
n² ∈ Ω(3n² + n log(n)) because 3n² + n log(n) ∈ O(n²)
... and so on...

Therefore, Big-Omega gives only one side of information,

1. It says T(n) is in some sense at least f(n) but it could be way way more...
2. It also says that your algorithm is at least this bad. Whereas Big-Oh says, your algorithm is at least this good. 
3. It describes the best that can happen for a given data size.

Q.1. Prove that running time T(n) = n³ + 20n is Ω(n²)

Sol. According to the definition of Big-Omega T(n)≥ Ω(f(n))
⇒  T(n) ≥ Ω(n²)
⇒  T(n) ≥ d.n²
⇒   n³ + 20n ≥ d.n²
⇒  
 The L.H.S of this inequality has the min. value of 8.94
for 4.47.

Therefore, the big-Omega condition holds for and 

Larger value of N results in larger factors d (e.g., for N=10 ). But, in any case above statement is valid.