45 votes 45 votes Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that $f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$. Which one of the following statements is FALSE? $f(n) + g(n) = O(h(n) + h(n))$ $f(n) = O(h(n))$ $h(n) \neq O(f(n))$ $f(n)h(n) \neq O(g(n)h(n))$ Algorithms gateit-2004 algorithms asymptotic-notation normal + – Ishrat Jahan asked Nov 2, 2014 • edited Jun 24, 2018 by Shikha Mallick Ishrat Jahan 13.2k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Akash Papnai commented Jul 6, 2020 reply Follow Share @Avir Singh Take f(n) = log n , g(n) = n , h(n) = n. And then solve the question. 0 votes 0 votes sanjaysharmarose commented Aug 9, 2020 reply Follow Share In option A f(n)+g(n)=O(h(n)+h(n)) f(n)+g(n)=O(2(h(n))) f(n)+g(n)=O(h(n)) f(n)+g(n) <= h(n) Now since h(n)= Θ(g(n)) f(n)+h(n) <= h(n) It is false as LHS is greater than RHS. How this procedure is wrong??? 0 votes 0 votes Sankalptiwari commented Sep 10, 2020 reply Follow Share Here we are checking the order so the greater order will be the overall order in LHS n^2 +n^3 = O(n^3) as on LHS n^3 is greater only this will be evaluated and the smaller terms would be ignored in comparison so n^3 = O(n^3) which is correct similarily f(n)+g(n) = O(h(n)) g(n) = O(h(n)) which is correct 3 votes 3 votes Please log in or register to add a comment.
Best answer 40 votes 40 votes Answer is (D). We can verify as : $f \leqslant g$ but $g \nleqslant f$. Therefore, $f<g$. Also, $g=h$, as $g=O(h)$ and $h=O(g)$. Sandeep_Uniyal answered Jan 17, 2015 • selected Dec 2, 2018 by Manu Thakur Sandeep_Uniyal comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments nttarun commented Jun 12, 2020 reply Follow Share but why is option D is false suppose f(n) = n, g(n) = n^2 , h(n) = n^2, then f(n)h(n) = n*n^2 = n^3 O(g(n)h(n)) = O(n^2 * n^2 ) = O(n^4) so is not n^3 = O(n^3) ? 1 votes 1 votes sanjaysharmarose commented Aug 9, 2020 reply Follow Share Option D says f(n)h(n)≠O(g(n)h(n)). What you are telling is f(n)h(n)=O(g(n)h(n)) which is true. Hence option D is false. 0 votes 0 votes AASTHA CHANDRA commented Jul 19, 2022 reply Follow Share o means O also so B is correct 0 votes 0 votes Please log in or register to add a comment.
27 votes 27 votes LETS ASSUME f(n)= n, g(n)=n^2, h(n)=n^2 option A: n+n^2=O(n^2+n^2)------- TRUE option B: n+n^2=O(n^2)------------------ TRUE option C n=O(n^2)------------- TRUE option D n.n^2 != O(n^2 * n^2)= n^3!= O(n^4)----------- FALSE hence D the answer sushmita answered Apr 13, 2017 sushmita comment Share Follow See all 2 Comments See all 2 2 Comments reply shaz commented Dec 17, 2018 reply Follow Share You're actually saying that in option d: LHS != RHS thus making the statement TRUE, which is not the case. 1 votes 1 votes GopiChand commented Mar 20, 2021 reply Follow Share sir can u check option c one more tim e 0 votes 0 votes Please log in or register to add a comment.
20 votes 20 votes $f(n)=O(h(n))$ (Using transitivity) $h(n)=Ωf(n)$ $f(n) g(n)=O(g(n) h(n)$ is TRUE. So, $D$ is FALSE. Pooja Palod answered Nov 10, 2015 • edited Jun 24, 2018 by Shikha Mallick Pooja Palod comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments sourav. commented Jul 28, 2016 reply Follow Share option A: f(n)+g(n)=O(g(n)+h(n) [ g(n) = O(h(n)), and h(n) = O(g(n)) which proves g(n)=h(n) ] =g(n)+h(n) =O(h(n))+h(n) 0 votes 0 votes srestha commented Aug 7, 2016 reply Follow Share here it is asked to tell false. So, option D false.rt? 0 votes 0 votes sourav. commented Aug 7, 2016 reply Follow Share yep...!!option D is false and so is the Answer ! 2 votes 2 votes Please log in or register to add a comment.
6 votes 6 votes I think option a is mis printed And option d is false Bhagirathi answered Nov 8, 2014 Bhagirathi comment Share Follow See all 0 reply Please log in or register to add a comment.