edited by
17,265 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

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

0 votes
0 votes
Answer is D.
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...