retagged by
444 views

2 Answers

3 votes
3 votes
$f(n) = \Theta(g(n))$ and $g(n) = \Theta(h(n))$ implies $f(n) = \Theta(h(n))$ (by transitivity).

Now $f(n) = \Theta(h(n))$ implies $h(n) = \Theta(f(n))$ (symmetry property). So statement I is true.

Similarly in statement II, by transitivity, we get $f(n) = O(h(n))$ this implies $h(n) = \Omega(f(n))$, by transpose symmetry.

Statement III is false.  consider  $f(n) = n^2$ and $g(n)=4n^2$

Statement III would be true, if the conclusion was $f(n) = \Theta(g(n))$ or $g(n) = \Theta(f(n))$.

You can refer to these properties in CLRS.

Related questions

0 votes
0 votes
1 answer
1
2 votes
2 votes
1 answer
2
gauravkc asked Apr 5, 2018
855 views
What is the time complexity of this code?
3 votes
3 votes
1 answer
3
0 votes
0 votes
3 answers
4
pranab ray asked Jan 13, 2018
390 views
i am getting t.c as O(n^5) but given answer as O(n^4) what should be the answer