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

if f(n) = n^3 then your answer theta(n) fails

---

f(n)+g(n)-h(n)=O(n^3)
f(n)+g(n)-h(n)=omega(n)

thus option a is not correct.omegar(n^2) cant be true
option b is incorrect as it cant be O(n)
But it can be option c because it may take n units of time in average right ?
Correct me if i am wrong,I am not sure about this answer

---

since f(n) >= n
g(n) <= n
h(n) = n

theta(n) possible only if all are n but in all other cases it fails
Also we always takes worst cases in consideration not average
so answer must be D. None

---

Hmm ya .. thanks :)

---

@aehkn is right, ans is D option

---

Can anybody please explain why O(n) is incorrect ?

---

@abbas

Consider f(n) = $n^{2}$ , g(n) = log n, h(n) = n.

---

@hemant

Thanks, but according to above comments and yours too, in conclusion, we have if h f and g are independent functions, there can be infinite possiblities.

Correct me if i am wrong.

But wouldnt we consider that f(n) is defined, and that its lower bound can be equated to asymptotic linear value ? (Omega (n))

And similarly for g (n) we have a upper bound of O(n).

Meaning fn is some function which gives a value greater than n but can be lower bounded to n.

And gn is some function which gives a value less than n, but can be upper bounded to n.

So why are we considering quadratic and exponential functions ?

---

f(n) = $\Omega$ (n) means n is the lower bound.

Even we use Omega to show that f(n) is tightly lower bounded to n, but we do not explicitly mention how much tight? There is no problem to use f(n) as  $n^{2}$ or $n^{3}$ in such questions. Still lower bound is n. (which we need to maintain all the time).

---

f (n) >= n

g (n) <= n

c1.n <= h (n) <= c2.n

f (n) + g (n) is having

>=n + <=n

Best case : n + 0 = Omega (n)

Worst case: x.n + n = (x+1)n = O (n)

Since the value has both lower and upper bound in asyptotic (n) then we can safely say Theta (n)

Now, theta (n) - theta (n) simplifies to theta (n) only.

---

Bro, I'm sure about this, we can take f(n) = $n^{2}$ there is no problem in this assumption. If you are taking f(n) = log n. Then there is a big problem. :)

---

@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