2 votes 2 votes Let f (n) = Ο(n), g(n) = Ω(n) and h(n) = θ(n). Then g(n) + f(n).h(n) is ______ A.) Ω(n) B.) θ(n2) C.) Ω(n2) D.) θ(n) How to do these type of questions ? Algorithms made-easy-test-series algorithms asymptotic-notation + – ashish pal asked Jan 22, 2018 • edited Mar 5, 2019 by ajaysoni1924 ashish pal 709 views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Anu007 commented Jan 22, 2018 reply Follow Share $\Omega (n)$.... 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share To solve these questions you need to know asymptotic notations that's it 0 votes 0 votes ashish pal commented Jan 22, 2018 reply Follow Share @Mk Utkarsh I know asymptotic notations but these product terms( f(n).h(n) ) confuse me. Can you please tell me the approach 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share F(n) = O(n), somewhere inside that circle or on the line G(n) = Ω(n) somewhere outside or on the line H(n) = θ(n) exactly on the line of the circle So by the equation Ω(n) + O(n).θ(n) G(n) is somewhere outside but we don't know where so we don't know the exact location θ of this funtion also we cannot determine the Big Oh (upper bound ) because of the same reason somewhere outside but it can be exponential or idk. So only we can calculate Ω but how? Ω is lower bound so what can be the lower bound of f(n) = constant, g(n) = n and h(n) = n n + 1.n that's how we get Ω(n). Comment if you have any questions 1 votes 1 votes Sumaiya23 commented Jan 23, 2018 reply Follow Share How did u conclude f(n) = constant? Also, I did not understand the first three lines of your explanation. 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share F(n) $\leq$ n G(n) $\geq$ n H(n) = n these are the first three lines and lower bound of f(n) will be somewhere between constant and n n $\geq$ f(n) $\geq$ 1 f(n) $\geq$ 1 just rewrite in omega f(n) = Ω(1) 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share i never concluded f(n) = constant i was explaining the lower bound in layman words 0 votes 0 votes Sumaiya23 commented Jan 23, 2018 reply Follow Share Okay, i get it! I have another doubt, u said, "and lower bound of f(n) will be somewhere between constant and n", similarly, upper bound of G(n) can be n/n^2/2^n...but as that is not in the options, we go for Ω(n). Is this right? 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share No if there was another option O(2n) or O(n2) we cannot choose these with the given question because upper bounds are endless how can we decide if some algorithm is working at minimum n then it will work at max n2 , we cannot deicide just be lower bound. That is incomplete information for solving Big-Oh 0 votes 0 votes Sumaiya23 commented Jan 23, 2018 reply Follow Share Okay! Finally got it!! Thanks a lot!!! 1 votes 1 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share yeah but i agree upper bound of G(n) will be somewhere between n to anything like n3 , exponential or Exhaustive Search (n!) 1 votes 1 votes Hirak commented May 7, 2019 reply Follow Share @Mk Utkarsh how to calculate f(n).h(n) ??? 0 votes 0 votes srestha commented May 7, 2019 reply Follow Share https://gateoverflow.in/11232/let-f-n-ω-n-g-n-o-n-and-h-n-ѳ-n 1 votes 1 votes Please log in or register to add a comment.