search
Log In
0 votes
130 views
Consider the following statements:
S1: f(n) = O(f(n)²)
S2: If f(n) = O(g(n)) then ${2^{f(n)}}$ = O(${2^{g(n)}}$)
S3: If f(n) = O(g(n)) and h(n) = Ɵ(g(n)) then
f(n)•h(n) = O(g(n)•h(n))

 

Which of the statements are correct??

(A) only S2

(B) only S3

(C) both S1 and S2

(D) both S2 and S3.
in Algorithms 130 views
0
for 1, the counterexample is 1/n

for 2, the counterexample is f(n)=n, g(n)=n/2
0
Bro please explain a little more..
Not clear :(

1 Answer

1 vote
Option B is the answer
0
Explanation?
1
For s1 f(n)=1/n

For s2 we can take 2n and n

And s3 is right u Know properties
0
is S3 a property??

I never see it anywhere.
0
I mean u can write O and theta and solve
0
  • S1 is Not Hold For  f(n)= 1/n
  • S2 is Not Hold For

               F(n)=2logn and G(n)=logn​​​​​​  here f(n)=O(g(n))

                https://gateoverflow.in/260234/asymptotic-notations-with-condition?show=266187#c266187

  • S3 is Hold Because Of Upper Bound

Related questions

1 vote
1 answer
1
162 views
Q1) f(n) = n^(1-sin n) g(n) = n^(1+cos n) Relation between them ? Q2) f(n) = n^(1-sin n) g(n) = n^(2+cos n ) Relation between them ?
asked Mar 7, 2019 in Algorithms Ashish Roy 1 162 views
1 vote
3 answers
2
222 views
Which of the following is not true in the function $f(n)=2^{n-4}$? $f(n)$=Θ($2^{n+3}$) $f(n)$=Ω($n^{1000}$) $f(n)$=Ο($2^{n-10}$) $f(n)$=$None$
asked Dec 7, 2018 in Algorithms Gupta731 222 views
0 votes
1 answer
3
207 views
Consider the following function $f(x)$ = $x^8$+6$x^7$-9$x^5$-$x^4$+2$x^2$-18. Which of the following is true if x is greater than 56? $f(x)$ = O($x^8$) $f(x)$ = Ω($x^8$) $f(x)$ = θ($x^8$) $f(x)$ = None of the above.
asked Dec 7, 2018 in Algorithms Gupta731 207 views
1 vote
1 answer
4
179 views
Identify the FALSE statement: $A)$ $f(n)=\theta(f(\frac{n}{2})$ $implies$ $f(n^{2})=\theta(f(\frac{n^{2}}{2}))$ $B)$ $f(n)=O(g(n))$ $implies$ $log(f(n))=O(log(g(n)))$ where $n\geq2$ $C)$ $f(n)=O(g(n))$ $implies$ $2^{f(n)}=O(2^{g(n)})$ $D)$ $f(n)+g(n)=\theta(Max(f(n),g(n)))$
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 179 views
...