[Solved] CSE 2331 Homework 1

1. [30 points] Give the asymptotic complexity of each of the following functions in simplest terms. Yoursolution should have the form (n) or ((log(n))) or (n(log(n))) or (n) or (1) where, , , , are constants. (No need to give any justification or proof.)(a) fa(n) = log2(3n+2 + 5n3 + 1);(b) fb(n) = n0.1 lg(4n5 3n3) + 3n0.2;(c) fc(n) = 3 log4(4n + 1) log3 n + log2(6n2 + 8n);(d) fd(n) = 613 + 26 7 log4(62);(e) fe(n) = 2(n + 4) log3(2n3 + 1) + 5n +2n;(f) ff (n) = 15n 10n + n100;(g) fg(n) = 8n + 2n;(h) fh(n) = 3 5n+9 + 6 3n+9;(i) fi(n) = 2n3 + 3n2;(j) fj (n) = 9 2log2(n2+2n);(k) fk(n) = (3 log4(n2 + 8) + 6n) (log5 n + 4 log3 n);(l) fl(n) = 34n + 43n;(m) fm(n) = 5 log10(7n3 6n + 9) + 9 log2(5n4.5 + 33n);(n) fn(n) = (4n3 + 2n2 + 1) (n2 + 5n + 13) (12n 6);(o) fo(n) = log10(4n + 6n + 8n);2. [20 points]Rank the following functions by order of growth: that is, find an arrangement g1, g2, . . . ,of these functions such that either gi = O(gi+1) or gi = (gi+1), for any two consecutive functionsgi and gi+1 in your ordered list. (For example, given n, 2, 2n, 3n +n, your answer will look like:2 = O(n), n = (3n +n), and 3n +n = O(2n). ) You need to make your answer as tight as possible, that is, you should say gi = (gi+1) whenever possible. In what follows, lg refers to log2 and ln refers loge where e is the natural number. (No need to provide justificaiton and proof for your answers.)n lg n, 2n+9,p2n2 lg n + 3n, 2lg n, lg(n!), nln n, 5900,12 2n, 2 3n, n 2n,n0.7, lg(6n + 7) lg(5n0.3 + 21),pn3 2n2, 32n, log6((2n + 4)(3n + 2)(5n + 6)), 2ln n.3. [10 points]Specify whether each of the following statement is true or false. If it is true, prove it. If itis false, disprove it by providing a counter example. (All functions below are positive functions.)(a) If f(n) = O(g(n)), then f2(n) = O(g2(n)) (where f2(n) = f(n) f(n) and g2(n) = g(n) g(n)).(b) f(n) + g(n) = (min{f(n), g(n)}).4. [10 points] Provide an example in each of the following case, and briefly justify your answer.(a) Give an example of a function f(n) such that: f(n) O(n) and f(n) (log n) but f(n) 6(n) and f(n) 6 (log n).(b) Give an example of a function f(n) such that: f(n) O(12n log n) and f(n) (100n) butf(n) 6 ( 12n log n) and f(n) 6 (100n).5. [5 points] Prove that 73n5 9n3 + 2 (n2.5).1