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 Show 14 previous comments 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.