1.5k 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.5k 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 (294k points)
edited by

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 (423 points)