67 votes 67 votes Let $f(n) = n$ and $g(n) = n^{(1 + \sin \: n)}$, where $n$ is a positive integer. Which of the following statements is/are correct? $f(n) = O(g(n))$ $f(n) = \Omega(g(n))$ Only I Only II Both I and II Neither I nor II Algorithms gatecse-2015-set3 algorithms asymptotic-notation normal + – go_editor asked Feb 15, 2015 • edited Jun 24, 2018 by Shikha Mallick go_editor 17.7k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments akshay7797 commented Jan 25, 2020 reply Follow Share even for positive values of n, Sin n can be negative 4 votes 4 votes Abhishek Rauthan commented Jan 5, 2023 reply Follow Share if instead g(n)=n^(1+sin n) ,we have g(n)=n^(2+sin n) then sin n max value 1 (g(n)=n^2) and min value -1 (g(n)=n) so option 1 would be correct. 0 votes 0 votes Sin commented Jan 12 reply Follow Share here, use of the sentence "where n is a positive number" is about n being equal to 0, 45, 60, 90, 180, 270, 360 (not negative -45, -90 etc.,) here sinn (sin0, sin45, sin60, sin180 ) equals -1 to 1 note: sinn value can be positive or negative, n should be positive number is what meant 1 votes 1 votes Please log in or register to add a comment.
Best answer 87 votes 87 votes The answer is option (D). Since the value of $\sin(n)$ will always range from $-1$ to $+1$, hence $g(n)$ can take values $1$, $n$, $n^2$. Hence, if $g(n) = 1$, then statement I is incorrect. And, if $g(n) = n^2$, then statement II is incorrect. saurabhrk answered Feb 20, 2015 • edited Jun 24, 2018 by Shikha Mallick saurabhrk comment Share Follow See all 7 Comments See all 7 7 Comments reply Jonathan Decosta commented Jun 17, 2015 reply Follow Share What if we take g(n) = n ?..Then both are correct 6 votes 6 votes Arjun commented Jun 17, 2015 reply Follow Share Yes, obviously. Then we get $\Theta$ and $\Omega$ and $O$ will also be true. 10 votes 10 votes Jonathan Decosta commented Jun 17, 2015 reply Follow Share Then the answer is conflicting. Which one to choose between option 3 & 4 ? 1 votes 1 votes Arjun commented Jun 17, 2015 reply Follow Share Here g(n) is not n. It is $n^{1 + \sin n}$. So, D is correct. The complexity must be satisfied by ALL values of the function for large $n$. 23 votes 23 votes Jonathan Decosta commented Jun 17, 2015 reply Follow Share Thank u very much sir 4 votes 4 votes Pratyush Madhukar commented Jan 10, 2017 reply Follow Share This example is given in CLRS 3rd Ed. PN 52. The book clearly says (and explains) that these two functions are not comparable asymptotically. Those still in doubt can refer the book to understand. 16 votes 16 votes pramodborana112 commented Nov 24, 2017 reply Follow Share Since the value of sin(n) will always range from −1 to +1, hence g(n) can take values 1,n,n2 . Hence, if g(n)=1, Statement I is incorrect,But at same time statement 2 is correct. And, if g(n)=n2, then Statement II is incorrect,and here also statement 1 is correct. So option c or d,please explain. 0 votes 0 votes Please log in or register to add a comment.
16 votes 16 votes This exact example is given in CLRS 3rd Ed. PN 52, It clearly states that we can't compare these two fn using asymptotic notation so answer is option D Rishav Kumar Singh answered Aug 22, 2018 Rishav Kumar Singh comment Share Follow See all 2 Comments See all 2 2 Comments reply piya commented Aug 22, 2018 reply Follow Share Thanks you 1 votes 1 votes SANGAMESH017 commented Jul 20, 2020 reply Follow Share True, if g(n)=$n^{(1+|sin(n)|)}$ ans would be f(n)=O(g(n)) right? 1 votes 1 votes Please log in or register to add a comment.
10 votes 10 votes actually sinn oscillates between -1 and 1. So, g(n) has a range of values between 1 and n^2 i.e. g(n) = [1, n^2]. But we can't really compare f(n) and g(n) for large values of n. So, (D) is correct without a shadow of doubt. ravi_ssj4 answered Sep 3, 2016 ravi_ssj4 comment Share Follow See 1 comment See all 1 1 comment reply Ashwani Yadav commented Jan 19, 2019 reply Follow Share thnx 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes n f(n) g(n) 90 (90)^2 90 180 180 180 270 1 270 360 360 360 Here we can put different values of n ranging from 90 ,180 ,270 and 360 sometimes value of f(n) increases and sometimes g(n) ,so we cant say which one is greater or lesser. Sine curve graph OPTION D IS CORRECT chandnikrish answered Dec 19, 2016 chandnikrish comment Share Follow See all 2 Comments See all 2 2 Comments reply smartmeet commented Jan 24, 2017 reply Follow Share So if some function is lower-bound and upper-bound at same time for another function then we can't compare both of them, right? 1 votes 1 votes chandnikrish commented Jan 24, 2017 reply Follow Share Yup True. 1 votes 1 votes Please log in or register to add a comment.