2 votes 2 votes Given that, f(n) = O(g(n)) then it implies that h(f(n)) = O(h(g(n)). State TRUE/FALSE with proper Explanation/Examples.Please provide mathematical proof,don't just prove by giving a counter example Algorithms algorithms asymptotic-notation + – sourav. asked Jul 28, 2016 sourav. 3.5k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Prashant. commented Jul 28, 2016 reply Follow Share what u mean by mathematical proof,don't just prove by giving a counter example 1 votes 1 votes sourav. commented Jul 28, 2016 reply Follow Share i mean please mathematically express the question (i mean f(n)<=cg(n))and then put the given question in it and then give the example....i think it would be hard to find the counter example in the exam.. 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes $f(n) = O(g(n))$ means there exists an $N$ and $C$ such that $f(n) \leq C.g(n), \forall n > N$. Now, we apply a function $h$ on either side. Will the equation holds true? Case 1: Consider $f(n) = C. g(n), \forall n > N, C > 1$. Now, it is clear that value of $f(n) > g(n)$ for all large $n$ (though their growth rates are the same). So, if we take $h$ as any exponential function $h(f(n)) > h(g(n))$ or $h(g(n)) = o(h(f(n))$ (small o). The given statement is false. Case 2: We alreayd proved that the statement is false. Now, suppose the statement given says small-o $(<)$ and not big-O $(\leq)$. In this case the statement holds true provided $h$ is a strictly (monotonically) increasing function - i.e., as the input increases value of $h$ also increases. If we consider a decreasing function like $\frac{1}{x}$, then the statement is false. Arjun answered Aug 6, 2016 • edited Aug 28, 2016 by Arjun Arjun comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Aug 7, 2016 reply Follow Share if f(n)>g(n) their graowth rates are the same as u told then f(n) = O(g(n)) is also false then why do we prove h(f(n)) = O(h(g(n)) 0 votes 0 votes Arjun commented Aug 7, 2016 reply Follow Share If $f(n) > g(n)$, for all $n$, then $f(n) = O(g(n))$ is false This is not true. Consider $f(n) = 2n$ and $g(n) = 3n$.Here, $f(n) = O(g(n))$. When we say order of we are talking about growth rate, not actual values. i.e., why we ignore constant factor. But when we want to get actual value constants are important. Also, if the growth rate of a function is higher compared to other, its actual value will eventually grow higher and this is the mathematical statement of $f(n) \leq Cg(n), \forall n > N$, where $N$ represent the particular input point at which the higher growing function takes over the other. 1 votes 1 votes Sushant Gokhale commented Aug 28, 2016 reply Follow Share @Arjun. For case 1, if C<1, then g(n) > f(n), right? 1 votes 1 votes Arjun commented Aug 28, 2016 reply Follow Share Yes, that's a mistake. Corrected. Thanks. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It is TRUE Say, g(n)=n2 f(n)=log n Now put n=2x So, g(n)=22x f(n)=x So, f(n)=O(g(n)) Now, h(n)=n3 g(n)=(n2)3 f(n)=(log n)3=n6 Now, putting n=2x , we get h(g(n))=26x h(f(n))=x3 Hence proved h(f(n)) = O(h(g(n)). srestha answered Jul 28, 2016 • edited Aug 5, 2016 by srestha srestha comment Share Follow See all 17 Comments See all 17 17 Comments reply sourav. commented Jul 28, 2016 reply Follow Share it is false....please use example after mathematically proving it ..!! 0 votes 0 votes sourav. commented Jul 28, 2016 reply Follow Share take example h(n)=2^n 0 votes 0 votes Prashant. commented Jul 28, 2016 i edited by Prashant. Jul 28, 2016 reply Follow Share I don't know what mean by mathematical simple proof f(n) = 2n , g(n)= n now f(n)= O(g(n)) now take h(n) = 2n . now h(fn) = 22n h(g)= 2n clearly h(f(n)) ≠ O(h(g(n))) since h(f(n)) is 2n time bigger. 2 votes 2 votes srestha commented Jul 28, 2016 reply Follow Share then h(f(n)) =O( h(g(n)) ) rt? @Anirudh 0 votes 0 votes srestha commented Jul 28, 2016 reply Follow Share See if one function asymptotic growth rate is higher and putting them in another function , will their growth rate changes? 0 votes 0 votes Prashant. commented Jul 28, 2016 reply Follow Share http://stackoverflow.com/questions/12361448/i-need-help-proving-that-if-fn-ogn-implies-2fn-o2gn if one function asymptotic growth rate is higher and putting them in another function we can not comment about growth of new function. 0 votes 0 votes sourav. commented Jul 28, 2016 reply Follow Share problem1.1 d) https://dspace.mit.edu/bitstream/handle/1721.1/37150/6-046JFall-2004/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2004/CDF0CA1F-85EF-4FF4-933B-27E503A0AEA8/0/ps1sol.pdf 1 votes 1 votes Prashant. commented Jul 28, 2016 reply Follow Share i already gave counter example to make false. 1 votes 1 votes sourav. commented Jul 28, 2016 reply Follow Share (y) 0 votes 0 votes Tauhin Gangwar commented Jul 28, 2016 reply Follow Share anirudh u r correct...@srestha ur answer is wrong check it.. @sourav anand what is mathematical prove...anirudh explained well 0 votes 0 votes srestha commented Jul 28, 2016 reply Follow Share @Anirudh 22n>2n then why not h(f(n)) = O(h(g(n))) ? 0 votes 0 votes Tauhin Gangwar commented Jul 28, 2016 reply Follow Share @dear srestha plz don't be angry but ur concept is wrong f(n) = Og(n) means either g(n) is equal to f(n) OR g(n) is greater than f(n) 0 votes 0 votes srestha commented Jul 28, 2016 reply Follow Share ok we cannot say Big O for exponential limit.rt? 0 votes 0 votes Tauhin Gangwar commented Jul 28, 2016 reply Follow Share no u got wrong ..we can say 4 any function.. 2^2n = O(2^n)....is wrong. (2^n) = O(2^2n)...is right 0 votes 0 votes srestha commented Jul 29, 2016 reply Follow Share @Tauhin Acc to Anirudh link if it is not constant we cannot conclude big O 0 votes 0 votes Tauhin Gangwar commented Jul 29, 2016 reply Follow Share the link doesn't say we cannot conclude.... it says...by looking the ratio...we can tell it doesn't hold means...it is false.. 0 votes 0 votes ankit commented Aug 15, 2016 reply Follow Share @anirudh , by your example, It is showing false, but by srestha's example , it is showing true... please clear me the concept... 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes f = $x$ g= $x^2$ So, f = $O(g)$ Now, let 'h' be inverse function. So, $h(f)$ ≠ $O(h(g))$ Sushant Gokhale answered Aug 28, 2016 Sushant Gokhale comment Share Follow See all 0 reply Please log in or register to add a comment.