The value of sine function varies from -1 to 1. For sin = -1 or any other negative value, I becomes false. For sin = 1 or any other negative value, II becomes false

The Gateway to Computer Science Excellence

+39 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

+11

+54 votes

Best answer

+14

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$.

+10

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.

0

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, Statement I is incorrect,But at same time statement 2 is correct.

And, if g(n)=n^{2}, then Statement II is incorrect,and here also statement 1 is correct.

So option c or d,please explain.

+8 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.

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.

+5 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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,516 answers

195,579 comments

101,142 users