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

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

Comments

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

Answer 2

$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

Answer 3

We can't compare both functions. No doubt option D

Answer 4

Answer is D.

Comments

Explain otherwise upvote correct answer ...