ME test

Question

Let f(n) = Ω(n), g(n) = O(n), h(n) = θ(n). Then [ f(n) + g(n)] - h(n) is ______________ ?

A) Ω(n2)

B) O(n)

C) θ(n)

D) None

Answer 1

I am not sure about this.
f(n)=omega(n) which means its best case is n , so lets consider its worst case time complexity as nlogn
g(n)=O(n) which means max it takes n iterations or n units of time to execute
h(n)=theta(n) which means on an average it  takes n units of time to complete

O(f(n)+g(n)) means worst time case to complete f(n)+g(n) is O(n*logn)
omega(f(n)+g(n)) means best case time to complete f(n)+g(n) is omega(n+omega(g(n)),lets assume omega(g(n))=1.so best case is omega(n+1)=omega(n)

now O(f(n)+g(n)-h(n))=O(nlogn-n)=O(n*logn)
omega(f(n)+g(n)-h(n))=omega (n-n) but we cant say that same number of  steps are took in both (f(n)+g(n)) and h(n)
thus omega(f(n)+g(n)-h(n))=omega(n)

Thus its theta(n)

Comments

@hemant

I think you have a point, but, isnt there always a constant factor deviation?

I mean the definition states that

g (n) is in O (f (n)) if for a CONSTANT c,

g (n)<= c.f (n)

But why arent we taking the lower bounds in constants, but in n, n^2 etc ?

---

Brother i am sure you are correct, I just want to understand "How"

:P

---

I think O(n) is best answer since
f(n)  <= c1n  g(n) >= c2n  and h(n) = c3n
Worst case :  f(n) + g(n) == g(n)
                     and g(n) - h(n) == g(n)
Therefore Option (b) should be correct