Before reading this article I recommend you to read following articles:
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.,- Its used to express the lower bound of an algorithm's running time.
- It measures the best case time complexity i.e.,
- 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))
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)
n2 ∈ Ω(n) because n ∈ O(n2)
n2 ∈ Ω(3n2 + n log(n)) because 3n2 + n log(n) ∈ O(n2)
... and so on...
Therefore, Big-Omega gives only one side of information,
- It says T(n) is in some sense at least f(n) but it could be way way more...
- It also says that your algorithm is at least this bad. Whereas Big-Oh says, your algorithm is at least this good.
- It describes the best that can happen for a given data size.
Q.1. Prove that running time T(n) = n3 + 20n is Ω(n2)
Sol. According to the definition of Big-Omega T(n)≥ Ω(f(n))⇒ T(n) ≥ Ω(n2)
⇒ T(n) ≥ d.n2
⇒ n3 + 20n ≥ d.n2
⇒
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.
1 comment
The Star Casino: A New Experience | JTHub
The Star Casino 제주도 출장안마 - 상주 출장샵 A 시흥 출장마사지 New Experience. The Star 진주 출장안마 is one of the city's premier gaming venues offering something 광명 출장샵 for everyone. JT offers over 2500 slot and video
commentPost a Comment