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

asked in Algorithms by Loyal (4.2k points)   | 62 views
Answer should be D.

2 Answers

+3 votes
Best answer

mit quiz pdf link. here is the required part:

answered by Veteran (51.4k 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.4k points)  


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1528 Points

  10. rishu_darkshadow

    1512 Points


25,988 questions
33,561 answers
79,406 comments
31,026 users