4. For each assertion in 4(a)-(c), prove the assertion directly from the definition of the big-2 asymptotic notation if it is true by finding values for the constants c and no. On the other hand, if the assertion is false, give a counter-example. Then answer the question in 4(d). F denotes the set of all functions from Z+ to R+. (a) Let f(n): Z+R+. DEFINITION 1. A relation on a set is reflexive if each element is related to itself. Assertion: The relation "is big-2 of" is reflexive over F, In other words, f (n) S(f(n)). [5 points] Let f(n): Z+ R+ and g(n) : Z+ R". DEFINITION 2. A relation on a set is antisymmetric if whenever an element X is related to an element y and y is related X, then X = Y Assertion: The relation "is big-2 of" is antisymmetric over F In other words, if f(n) E (g(n)) and g(n) E (f(n)), then f(n)-g(n). [5 points] Let e(n) : Z+ DEFINITION 3. A relation on a set is transitive if whenever an element X is related to Y and Y is related Z, then X is related to Z. Assertion: The relation "is big-12 of" is transitive over F. In other words, if e(n) (f(n)) and f(n) e (g(n)), then e(nje (g(n)). [10 points] (b) (c) R", f(n) : +-+ R+ and g(n) : Z+-> R+. (d) Is "is big-12 of" a partial order on F? [5 points] DEFINITION 4. A relation is a partial order on a set if it is reflexive, antisymmetric and transitive 4. For each assertion in 4(a)-(c), prove the assertion directly from the definition of the big-2 asymptotic notation if it is true by finding values for the constants c and no. On the other hand, if the assertion is false, give a counter-example. Then answer the question in 4(d). F denotes the set of all functions from Z+ to R+. (a) Let f(n): Z+R+. DEFINITION 1. A relation on a set is reflexive if each element is related to itself. Assertion: The relation "is big-2 of" is reflexive over F, In other words, f (n) S(f(n)). [5 points] Let f(n): Z+ R+ and g(n) : Z+ R". DEFINITION 2. A relation on a set is antisymmetric if whenever an element X is related to an element y and y is related X, then X = Y Assertion: The relation "is big-2 of" is antisymmetric over F In other words, if f(n) E (g(n)) and g(n) E (f(n)), then f(n)-g(n). [5 points] Let e(n) : Z+ DEFINITION 3. A relation on a set is transitive if whenever an element X is related to Y and Y is related Z, then X is related to Z. Assertion: The relation "is big-12 of" is transitive over F. In other words, if e(n) (f(n)) and f(n) e (g(n)), then e(nje (g(n)). [10 points] (b) (c) R", f(n) : +-+ R+ and g(n) : Z+-> R+. (d) Is "is big-12 of" a partial order on F? [5 points] DEFINITION 4. A relation is a partial order on a set if it is reflexive, antisymmetric and transitive