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.5k 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.
4 votes 4 votes Answer is D. Take different values for sinn -0,90,180,270,360 . You will find out that for 0,90 f(n)>g(n) and hence f(n)=omega(g(n)) and at 180,270 g(n) is greater therefor f(n) < g(n) i.e f(n)=Big-oh(g(n)) .therefore nothing is possible Gate Sanyasi answered Apr 2, 2015 Gate Sanyasi comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Apr 2, 2015 reply Follow Share The above reason is actually not sufficient. We have to prove this for all large n. (Since sin x is a periodic function the above argument holds for all large n.) 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes $sin(n)$ ranges from $-1$ to $1$ (So does $cos(n)$) $f(n)=n$ $g(n)=n^{0 \ to \ 2}$ These are incomparable functions. For a function to be $O$ of some other function, there must exist a constant $n_0$ after which the function can act as an upper bound of the other function. Same concept can be extended to $\Theta \ or \ \Omega$ For any given $n$, $g(n)$ can be as large as $n^2$, or as small as $n^0=1$, or somewhere in between. $g(n)$ can't bound $f(n)$ So, Option D JashanArora answered Jan 25, 2020 JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes We can't compare both functions. No doubt option D tusharSingh answered Jan 24, 2021 tusharSingh comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Answer is D. ppm answered Feb 16, 2015 ppm comment Share Follow See 1 comment See all 1 1 comment reply Puja Mishra commented Oct 20, 2017 reply Follow Share Explain otherwise upvote correct answer ... 1 votes 1 votes Please log in or register to add a comment.