The Gateway to Computer Science Excellence
0 votes
57 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 by Boss (12.9k points) | 57 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
by Active (2.5k points)
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

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
50,737 questions
57,292 answers
198,230 comments
104,910 users