a) For each of the following relations, prove or disprove that it is 1) reflexive, 2) symmetric, 3) transitive. (10 Points) i) For a,bN, the relation R defined as (a,b)R if and only if ab=. b) For a,bN, the relation R defined as (a,b)R if and only if kZ,a=3kb. Prove that R is an equivalent relation, and identify all elements of the set [3]{xRx9}{xRx20.01} (where [3] denotes the equivalence class containing 3). (10 Points) 5b) Prove that 2x=x+x+0.5 holds for any xR. (5 Points) Question 6 (25 Points): asymptotic scaling of functions (O1, O2) a) Prove the following statements. (10 Points) i) f(n)=log2(log2n) is O(0.1log2n). ii) f(n)=ln(n!+nn) is (nlnn). b) Let f(n):NR+be a generic positive function. Is it always true that f(n)=O(f(n)) ? Prove your claim. (5 Points) c) Let f be a positive function such that f(n)=af(n/b)+c holds for every integer n1, where a1, b is an integer larger than one, and cR+. Proof that f(n)=O(nlogba) if a>1, and f(n)=O(lnn) if a=1 (10 Points)