First time here? Checkout the FAQ!
+6 votes

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 in Algorithms by Boss (9.7k points)   | 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

2 Answers

+12 votes
Best answer
$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??


0 votes
[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)

answered by (423 points)  

Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2064 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points

26,038 questions
33,647 answers
31,069 users