Question

Let $f(n)= Ω(n), g(n)= O(n)$ and $h(n)= Ѳ(n)$. Then $[f(n). g(n)] + h(n)$ is:

• A. Ω (n)
• B. O (n)
• C. Ѳ (n)
• D. None of these

Comments

Any process without any assumptions?

---

https://cs.stackexchange.com/questions/101328/let-fn-omegan-gn-on-and-hn-thetan-then-fn-gnhn-is#comment216175_101328 A is correct.

---

how did you assume f(n) is Ω(1)  and h(n) is Ω(n)?

Answer 1

$f(n) . g(n)$ - here the individual bounds are ≥n and ≤n respectively. So, for their product we can just say it is ≥ n or Ω(n) provided $g$ is a non-decreasing function. But $(h = \Theta(n))  \implies \left[h = O(n) \text{ AND } h = \Omega(n)\right]$.

So,$$[f(n). g(n)] + h(n) = \Omega(n).$$
(whatever be the complexity of $f(n).g(n)$, $h(n)$ grows at least at the rate of $n$ and hence the whole expression too, due to '+')

Comments

none of these... ans is d

We can not say about function which are may be increase or decrease

---

which function here is may increase or decrease?

---

Sir if f(n)= theta(n) and g(n)= O(n) then f(n)*g(n)= O(n) , right or wrong ?

---

No.

(= n) . (≤ n) = ( ≥ n) and ≤ (n² )

i.e., Ω(n) and O(n²)

---

Sir actually I am having confusion in solving such computations, I am not getting the intution of finding out what would be the result of the product ,I mean if we multiply theta(n)*omega(n) then it is equal to omega(n) acceptable but theta(n) *O(n) =O(n^2) ,couldn't get this , sorry sir but I am stucked up in such computations.

---

Solve as in numbers. I say x = 5 and y ≤ 25. Now, x * y = ? (Assume x, y ≥ 1)

We can say it is ≥ 5 and ≤ 125 rt?

---

Ω(n) + Θ(n) = Ω(n)

Explain this part plz @Arjun Sir

---

x > 5. y = 100. Now, x + y ? surely > 5 rt? Same analogy.

---

Got it thank you Sir

---

Sir about original question, how is Ω(n)*O(n)=Ω(n)  ?

we cants say anything right? 

lets say n = 5, then x = 6 = Ω(n) 

and y = -6 = O(n)

then x.y = -36 it is not Ω(n) right? Am I correct?

---

Ω(n)= {n, .nlogn,.. n^2,.. n^3,..} O(n)= {1,.. logn, ...n} so mutiply can us give n, so Ω(n)

---

@Mahesha You are right. Here, I should have considered decreasing functions like $\frac{1}{n}$ which would decrease the value of functions on multiplication. Corrected now.

---

☊(n) + O(n)=☊(n).. right or wrong??

---

right.

---

@Arjun Sir

I havenot got this line

$h = \Theta(n)  \implies h = O(n) \wedge h = \Omega(n)$

Please explain

Do u mean , for every $\Theta \left ( n \right )$ and non decreasing function $\Theta \left ( n \right )=$$\Omega \left ( n \right )$

How is it possible?? 

---

Isn't it the definition of Theta notation?

---

How??

$\Theta$ is stronger notation than $O.$ and $\Theta$ is asymptotically tight bound. Then how can we say

$O\wedge \Theta =\Omega$ ??

---

got it :)

---

Sir, I just wanted to confirm what I have understood from all the above conversation. Plz let me know if all below statements are correct or not.

We can write :
O(n) as f(n) <= n

Ω(n) as f(n) >= n

Φ(n) as f(n) = n

Is this all correct ?

Answer 2

Another approach (BY TAKING EXAMPLE):-

Let $f(n) = An^2+Bn$ so $f(n)=Ω(n)$ is satisfy , $g(n) = Cn+D $ and $h(n) = En $

Now $f(n).g(n) = ( An^2+Bn).(Cn+D)  = Fn^3 + Gn^2+Hn ⇒ Ω(n) $

$f(n).g(n) +h(n)  = Fn^3 + Gn^2+Hn + En ⇒ Ω(n) ,O(n^3)  $

OPTION A

Comments

nice approach sir

Answer 3

Let us think it a bit practically..

We know

If we have modules having time complexities T₁ and T₂ , then time complexity of entire program = max(T₁ , T₂)

Keeping this in mind ,

Let T₁ corresponds to f(n) and T₂ corresponds to g(n) .h(n)..

So f(n) is guaranteed to be linear as f(n) = θ(n) ..

And g(n).h(n) if becomes larger than f(n) then the entire complexity becomes greater than function of n..It will have higher powers of n.So in that case it gives ω(n)..(Small Omega n)..

However if we have this product less than linear function of n , then we need not bother as f(n) is there to make for it..So in that complexity becomes θ(n)..

So considering the above two cases we can say that overall complexity or in other words the function f(n) + g(n).h(n)  = Ώ(n)..Hence C) is the correct answer..

Comments

u say that θ(n) + ω(n) = Ώ(n)

 but here maximum (θ(n) , ω(n)) =  ω(n) ?? plz check

and i am  not get how g(n).h(n)= ω(n) ????

---

By that I mean to say big omega is nothing but it is combination of small omega and theta..As theta gives tightest lower bound and small omega gives not tight (strict) lower bound..

But big omega simply gives lower bound..It may be tight or not tight bound..That is what I meant by that statement..

Answer 4

..............

Comments

@abhishekmehta4u

We can't say for sure that complexity is O(n^2)

As g(n) is omega (n), not O(n)

When we don't know the upper bound of g(n), we can't find out the upper bound of g(n).h(n)

However, we can say that it can be omega(n) for sure, at least.

---

can u explain the steps i am not able to understand  how does u get ???

if any links available then also it will be nice !!

@abhishekmehta4u

---

@vijju

what is the max and min value for this term [g(n)*h(n)] , min would be n as g(n) cant go below n and h(n) can become constant that case would give minimum value,

now think what can be its max value,you cant predict it

so for term [g(n)*h(n)] what you can surely say is its minimum value would be n, i.e  omega(n)

now total exprsn is f(n)+[g(n)*h(n)], f(n) is theta(n) , it cant go beyond n or less than n ,so what you can say from total exprsn that value of this exprsn will always be greater or equal to n i.e omega(n)