edited by
595 views
1 votes
1 votes
Let $f(n)$ = Ω(n) and g(n) = O(f(n)). Then g(n) = _______ [Assume n>0 ]

(a.) Ω(n)

(b.) O(n)

(c.) θ(n)

(d.) Ω(1)

 

According to me, the answer should be (b.) since, f(n) has lowest bound n and g(n) has f(n) as upper bound. Answer given is (d.)

I am confused about the answer.
edited by

1 Answer

Best answer
1 votes
1 votes
Ans is omega(constant) because f(n)>=c.n and g(n)<=c1.n and g(n)=O(f(n)) .Take a scenario where g(n) s a constant value so it is loosely bounded by Bigoh of f(n) then g(n)= omega(1) stands ..

take another scenario where g(n)=n+1 and f(n) be n+1/n^2/n^3 ,still omega(1) holds. since  we cannot be sure of the upper limit of f(n) so g(n)  cannot be O(n).
selected by
Answer:

Related questions

2 votes
2 votes
0 answers
2
ashish pal asked Jan 22, 2018
651 views
Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______A.) Ω(n)B.) θ(n2)C.) Ω(n2)D.) θ(n)How to do these type of questions ?
0 votes
0 votes
0 answers
3
0 votes
0 votes
2 answers
4
Anusha Motamarri asked Dec 5, 2016
1,459 views
what if i take f(x) = sinx,g(x)= cosx?these two cant be compared.sinx cant be written as O(cosx) and also cosx cant be written as O(sinx)then B becomes invalid.plz verify...