[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) = 8√n + 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) + 6√n) × (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!), n√ln 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(12√n log n) and f(n) ∈ Ω(100√n) butf(n) 6∈ Θ( 12√n log n) and f(n) 6∈ Θ(100√n).5. [5 points] Prove that 7√3n5 − 9n3 + 2 ∈ Θ(n2.5).1