1 votes 1 votes f(n) = O(g(n)) and g(n) = O(f(n)),then f(n) = g(n) ---> True or False The answer to this question is False and this the explanation given by them " False: f(n) = n and g(n) = n+1". Someone please explain what are they trying to say. amitqy asked Aug 21, 2018 amitqy 393 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Anand. commented Aug 21, 2018 reply Follow Share Taking your example only $f(n)=n$ $g(n)=n+1$ Given $f(n)=O(g(n))\Rightarrow f(n) <=c_1 g(n)$ if we take $c_1=1$, it holds Now Given $g(n)=O(f(n))\Rightarrow g(n)<=c_2 f(n)$ it too holds if we take $c_2>=2$ so given both $g(n)=O(f(n))$ and $f(n)=O(g(n))$ ,it is proved that $f(n)\neq g(n)$ 3 votes 3 votes Rishav Kumar Singh commented Aug 21, 2018 i edited by Rishav Kumar Singh Aug 21, 2018 reply Follow Share See, it need not be always that f(n) = g(n) If it has been asked f(n) != g(n) Then also it will be false. 2 votes 2 votes Anand. commented Aug 21, 2018 reply Follow Share yes you are right , i just proved that both $f(n)$ and $g(n)$ can be unequal. 0 votes 0 votes amitqy commented Aug 21, 2018 reply Follow Share If two functions are asymtotically equal,that does not mean they are mathematically equal.Can this be inferred ? 0 votes 0 votes Rishav Kumar Singh commented Aug 21, 2018 reply Follow Share Yes correct, lets take f(n) = n+6 g(n) = n+3 Both are mathematically unequal But both are of O(n) 0 votes 0 votes Sumit Singh Chauhan commented Aug 21, 2018 reply Follow Share All the confusion in this is because of mathematical and assymptotically equivalence. They are assymptotically equal but not mathematically. You can refer Anand's explanation for more clarification. He did it perfectly. 0 votes 0 votes Please log in or register to add a comment.