GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
55 views

asked in Algorithms by Active (2.3k points)   | 55 views
Answer should be D.

2 Answers

+3 votes
Best answer

mit quiz pdf link. here is the required part:

answered by Veteran (41.3k points)  
selected by
+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.
answered by Loyal (3.3k points)  

Related questions

+2 votes
0 answers
2
asked in Algorithms by Null&Void Active (1.8k points)   | 45 views
Top Users Feb 2017
  1. Arjun

    5410 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,864 questions
26,030 answers
59,704 comments
22,144 users