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 Chhotu commented Aug 6, 2017 reply Follow Share g = ϴ (h) or h = ϴ(g). I think we should not say g=h. am i correct ? 7 votes 7 votes Hemant Parihar commented Aug 6, 2017 reply Follow Share @chhotu. we can say that asymptotically they are equal. Suppose g(n) = 2$n^{2}$ and h(n) = 3$n^{2}$. g(n) = O(h(n)). h(n) = O(g(n)) $\Rightarrow$ g(n) = $\theta (h(n))$ Here g(n) and h(n) are asymptotically equal. 18 votes 18 votes Rupendra Choudhary commented Oct 10, 2017 reply Follow Share we can say f and g have same order of growth ...they are not same by value but same by order.. like f=2n+4 and g=n-5 2 votes 2 votes rajatmyname commented May 2, 2018 reply Follow Share @sandeep_uniyal I think this question is ambiguous because if you see second option it is given that f(n)=O(h(n)) which means f(n)<=h(n). But f(n) can never be equal to h(n). So second option should also be false apart from option d 1 votes 1 votes ankitgupta.1729 commented Sep 29, 2018 i edited by ankitgupta.1729 Sep 29, 2018 reply Follow Share I think option (C) is also FALSE. Please correct me where I am wrong. Here, $f(n) = O(g(n)) \; and \; g(n) \neq O(f(n)) \Rightarrow only \; f(n) \leqslant c*g(n) , c>0$ is true Now , $g(n) = O(h(n))$ means $g(n) \leqslant c_{1}* h(n)$ and $h(n) = O(g(n))$ means $h(n) \leqslant c_{2}* g(n)$ $\Rightarrow \frac{1}{c_{2}}*h(n) \leqslant g(n)$ $\Rightarrow c_{3}*h(n) \leqslant g(n)$ , here, all $c_{1},c_{2},c_{3}$ are $>0$. So, $c_{3}*h(n)\leqslant g(n) \leqslant c_{1}* h(n)$ means $g(n) = \Theta (h(n))$ Now . here , $g(n) \leqslant c_{1}* h(n)$ and $f(n) \leqslant c*g(n)$ implies $f(n) \leqslant c*c_{1}*h(n)$ i.e. $f(n) \leqslant c_{4}*h(n) , c_{4}>0$ So, we can say that $f(n)= O(h(n))$ Now , $c_{3}*h(n)\leqslant g(n)$ and $f(n) \leqslant c*g(n)$ From these 2 facts , it maybe possible that $c_{3}*h(n)\leqslant c_{5}*f(n)$ ,$c_{5}>0$ So, $c_{3}*h(n)\leqslant c_{5}*f(n)$ means $h(n) \leqslant \frac{c_{5}}{c_{3}}*f(n) \Rightarrow h(n) \leqslant c_{6}*f(n)$ , $c_{6}>0$ So, $h(n) \leqslant c_{6}*f(n)$ , $c_{6}>0$ means $h(n) = O(f(n))$ So, both $f(n) = O(h(n))$ and $h(n) = O(f(n))$ are possible. So, I think, we can't say $h(n) \neq O(f(n))$ is always true. 2 votes 2 votes Soumya29 commented Sep 30, 2018 i edited by Soumya29 Sep 30, 2018 reply Follow Share @ankit, $f(n)=O(g(n)) \ and \ g(n)≠O(f(n)) ⇒ \ 0 \leq f(n) < c∗g(n), \forall c>0 \ i.e \ f(n) = o(g(n)). $ $g(n)⩽c_1∗h(n) \ and \ f(n) < c∗g(n) \ implies \ f(n) < c∗c_1∗h(n)$ which means $f(n)= o(h(n)) \ and \ f(n)= o(h(n)) \Rightarrow h(n) \neq O(f(n)) $ 3 votes 3 votes ankitgupta.1729 commented Sep 30, 2018 i edited by ankitgupta.1729 Sep 30, 2018 reply Follow Share @Soumya $g(n) \leqslant c_{1}*h(n)$ is valid for some positive nonzero constant '$c_{1}$' and $f(n) \leqslant c*g(n)$ is valid for for all positive non-zero constants '$c$' .right ? Now , can you please explain in $f(n) < c*c_{1} * h(n)$ , how is it valid for all positive non-zero $c*c_{1}$ because you have written $f(n) = o(h(n))$ here, graph of $g(n)$ is above $f(n)$ for all positive constants '$c$' and $g(n)$ is sandwiched b/w $c_{1}*h(n)$ and $c_{3}*h(n)$ means graph of $g(n)$ is b/w a function $h(n)$ with some constant multiple and we don't know the relation between $f$ and $h$. So , Is not there a possibility that graph of $h(n)$ is below the graph of $f(n)$ for some positive constant $'c'$ ? 1 votes 1 votes Soumya29 commented Oct 1, 2018 reply Follow Share @Ankit, $g(n)⩽c1∗h(n)$ is valid for some positive nonzero constant $'c1'$ and $f(n)⩽c∗g(n)$ is valid for for all positive non-zero constants $'c'$ .right ? Right. here, graph of $g(n)$ is above $f(n)$ for all positive constants $'c'$ and $g(n)$ is sandwiched b/w $c1∗h(n)$ and $c3∗h(n)$ means graph of $g(n)$ is b/w a function $h(n)$ with some constant multiple Yes. Also graph of $h(n)$ is sandwiched between a function $g(n)$ with some positive constant multiples, say $c0 \ and \ c2$. $c0*g(n) \leq h(n) \leq c2*g(n) $ This says graph of $h(n)$ is always lie above graph- $c0*g(n)$ Is not there a possibility that graph of h(n) is below the graph of $f(n)$ for some positive constant ′c′ ? Suppose, yes there is a possibility. Then we will have $ h(n) \leq c4*f(n) \ or \ \frac{1}{c4}*h(n) \leq f(n).$ Also we have- $c0*g(n) \leq h(n), \\so,\\ \frac{1}{c4}*c0*g(n) \leq f(n) \ i.e \ c5*g(n) \leq f(n) \ where \ \ \frac{1}{c4}*c0 = c5. $ But graph of $f(n)$ always lie below $g(n) \forall \ c.$ So this contradicts our assumption that there exist some positive constant $c4 \ s.t \ h(n) \leq c4*f(n)$ 3 votes 3 votes 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.