edited by
17,263 views
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?

  1. $f(n) = O(g(n))$
  2. $f(n) = \Omega(g(n))$
  1. Only I
  2. Only II
  3. Both I and II
  4. Neither I nor II
edited by

11 Answers

Best answer
86 votes
86 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.

edited by
15 votes
15 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

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

Image result for sine curve graph

OPTION D IS CORRECT

Answer:

Related questions

57 votes
57 votes
5 answers
1
60 votes
60 votes
5 answers
3
44 votes
44 votes
5 answers
4
go_editor asked Feb 15, 2015
10,736 views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...