The Gateway to Computer Science Excellence
+45 votes
5.7k views

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
in Algorithms by
edited by | 5.7k views
+16
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
0
I want to ask what is the use of the sentence "where n is a positive number".

My doubt is if n is a positive integer, then sin n can take the only value as 1.So, the function g(n)= O(n^2).

Please correct me.
+1

if n is a positive integer, then sin n can take the only value as 1

why ?

+1

here basically we can't find $n_{0}$, right ??

+2
yes. right.
0
No, I mean, as we know the range of values of sin n is between (-1 to 1). As here, it is mentioned that 'n' should be a positive integer. So, I was thinking that we should calculate the range from 0+ to 1.
+1
even for positive values of n, Sin n can be negative

7 Answers

+61 votes
Best answer

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.

by
edited by
+5
What if we take g(n) = n ?..Then both are correct
+7
Yes, obviously. Then we get $\Theta$ and $\Omega$ and $O$ will also be true.
0
Then the answer is conflicting. Which one to choose between option 3 & 4 ?
+16

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

+4
Thank u very much sir
+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,n2 .

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

And, if g(n)=n2, 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.
by
0
thnx
+6 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

by
+1
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?
+1
Yup True.
+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
by
+1
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.)
0 votes
Answer is D.
by
+1
Explain otherwise upvote correct answer ...
0 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

by
0 votes

 

Neither I or II

Hope this helps:)

by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,586 answers
202,006 comments
95,409 users