1.6k views

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

1. Ω (n)
2. O (n)
3. Ѳ (n)
4. None of these
asked | 1.6k views

sir how can be

f(n) . g(n)  =  Ω(n)    ?

Sorry, that's true only for non decreasing functions. But answer won't change here.
i am not getting it need well good explaination please explain properly

$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 h = O(n) \wedge h = \Omega(n)$. 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 '+')
answered by Veteran (326k points)
edited by
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 ≤ (n2 )

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

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.
[f(n).g(n)] + h(n)

[O(n).☊(n)] + ⊖(n)       //* since b/w O(n) and ☊(n) .........O(n) is the dominating one*//

O(n) + ⊖(n)

O(n)
answered by (429 points)