CSE 2331 Homework 1 Autumn, 2017 (Total 75 points) 1. [30 points] Give the asymptotic complexity of each of the following functions in simplest terms. Your solution 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 + 5n 3 + 1); (b) fb(n) = n 0.1 × lg(4n 5 − 3n 3 ) + 3n 0.2 ; (c) fc(n) = 3 log4 (4n + 1) × log3 n + log2 (6n 2 + 8n); (d) fd(n) = 613 + 26 × 7 log4 (62); (e) fe(n) = 2(n + 4) log3 (2n 3 + 1) + 5n + √ 2n; (f) ff (n) = 15n − 10n + n 100; (g) fg(n) = 8 √ n + 2n; (h) fh(n) = 3 × 5 n+9 + 6 × 3 n+9; (i) fi(n) = √ 2n3 + 3n2; (j) fj (n) = 9 × 2 log2 (n 2+2n) ; (k) fk(n) = (3 log4 (n 2 + 8) + 6√ n) × (log5 n + 4 log3 n); (l) fl(n) = 34n + 43n; (m) fm(n) = 5 log10(7n 3 − 6n + 9) + 9 log2 (5n 4.5 + 33n); (n) fn(n) = (4n 3 + 2n 2 + 1) ∗ (n 2 + 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 functions gi and gi+1 in your ordered list. (For example, given n, 2, 2 n, 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, 2 n+9 , p 2n2 lg n + 3n, 2 lg n , lg(n!), n√ ln n, 5 900 , 1 2 · 2 n , 2 · 3 n , n · 2 n , n 0.7 , lg(6n + 7) × lg(5n 0.3 + 21), p n3 − 2n2, 3 2n , log6 ((2n + 4)(3n + 2)(5n + 6)), 2 ln n . 3. [10 points]Specify whether each of the following statement is true or false. If it is true, prove it. If it is false, disprove it by providing a counter example. (All functions below are positive functions.) (a) If f(n) = O(g(n)), then f 2 (n) = O(g 2 (n)) (where f 2 (n) = f(n) ∗ f(n) and g 2 (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( 1 2 √ n log n) and f(n) ∈ Ω(100√ n) but f(n) 6∈ Θ( 1 2 √ n log n) and f(n) 6∈ Θ(100√ n). 5. [5 points] Prove that 7√ 3n5 − 9n3 + 2 ∈ Θ(n 2.5 ). 1