GATE CSE 2015 Set 3 | Question: 42

Question

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?

1. $f(n) = O(g(n))$
2. $f(n) = \Omega(g(n))$

• A. Only I
• B. Only II
• C. Both I and II
• D. Neither I nor II

Comments

even for positive values of n, Sin n can be negative

---

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.

---

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 

Answer 1

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.

Comments

Thank u very much sir

---

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.

---

Since the value of sin(n) will always range from −1 to +1, hence g(n) can take values 1,n,n² .

Hence, if g(n)=1, Statement I is incorrect,But at same time statement 2 is correct.

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

So option c or d,please explain.

Answer 2

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

Comments

Thanks you

---

True,

if g(n)=$n^{(1+|sin(n)|)}$ ans would be f(n)=O(g(n)) right?

Answer 3

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.

Comments

thnx

Answer 4

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

Comments

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?

---

Yup True.