0 votes 0 votes let us consider f(n) is log(n) and g(n) = n and h(n) = n^2. since logn<= n n2 >= n for all values so given above equality holds true but when we substitute n+((logn)(n2) = O(n2) but ans is Ω(n) can somebody wxplain this plz Algorithms algorithms asymptotic-notation + – saurav04 asked Jan 22, 2015 saurav04 2.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes You can also take h(n) = n3, and then the upper bound changes. But whatever you take the lower bound of f(n) won't change and remains n because of the θ(n) term. Arjun answered Jan 22, 2015 selected Dec 24, 2017 by junaid ahmad Arjun comment Share Follow See all 4 Comments See all 4 4 Comments reply khushtak commented Dec 15, 2015 reply Follow Share i found a solution i have some problems regarding that solution f(n)=O(n), g(n)=Ω(n) , h(n)=Θ(n). g(n)+h(n).f(n) = Ω(n) +O(n).Θ(n) = Ω(n) +[Θ(n) <-->Θ(n2) ] what is the meaning of the [Θ(n) <-->Θ(n2) ] ? As i think , that means the value of O(n).Θ(n) can vary between Θ(n) to Θ(n2) or we can say like O(n) can be 1 or n. and Θ(n) can be n =Ω(n) the above equation Ω(n) +[Θ(n) <-->Θ(n2) ] results in Ω(n) . how? is it like we should opt higher function or Max(Ω(n) , [Θ(n) <-->Θ(n2) ] ) and Ω(n) will have higher value than Θ(n) or Θ(n2) ??http://math.stackexchange.com/questions/267252/how-to-prove-that-maxfn-gn-thetafn-gn 0 votes 0 votes Arjun commented Dec 15, 2015 reply Follow Share If we just use the English meaning of the symbols, it becomes very easy. $\Omega$ refers to asymptotically lower or equal. So, $f$ is either asymptotically growing equal as $n$ or is growing faster than $n$- we do not know how much faster. Similarly, $O(n)$ does no say how much slower. 1 votes 1 votes amitqy commented Aug 19, 2018 reply Follow Share please check my approach---> let n=25. For f(n), n<=25. Take n=18. For g(n),n=25.Take n=25 For h(n),n>=25.Take n=35 f(n). h(n)+f(n) = 18*35+18=646 646=omega(25) as for f(n) = omega(n) . n can be greater than or equal to n 0 votes 0 votes amcodes18 commented Feb 2, 2020 reply Follow Share U said h(n) can be n^3 anything . Now given that h(n)=Omega(n) , but don't we have to chose tightest lower bound . I mean for h(n) to be n^3 , the question writer would have written h(n) = Omega(n^2) . Then The Tightest Could Have been n^3. 0 votes 0 votes Please log in or register to add a comment.