UGC NET CSE | October 2022 | Part 1 | Question: 15

Question

Assume that $f(n)$ and $g(n)$ are asymptotically positive. Which of the following is correct?

• A. $f(n)=O(g(n))$ and $g(n)=O(h(n)) \Rightarrow f(n)=\omega(h(n))$
• B. $f(n)=\Omega(g(n))$ and $g(n)=\Omega(h(n)) \Rightarrow f(n)=O(h(n))$
• C. $f(n)=o(g(n))$ and $g(n)=o(h(n)) \Rightarrow f(n)=o(h(n))$
• D. $f(n)=\omega(g(n))$ and $g(n)=\omega(h(n)) \Rightarrow f(n)=\Omega(h(n))$

Comments

ans id  1427 is correct

---

f(n)>g(n)   and  g(n)>h(n) then f(n) >h(n)

Answer 1

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time.
It measures the best case time complexity or the best amount of time an algorithm can possibly
take to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
According to Transitive Property
f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n)) is Correct