Quiz 2 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the n-th harmonic number; thus, Hn=1/1+1/2+..+1/n (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) ogn 6O90 7+1 2H In n 6OΩ 0.01 100 n 6OΩ Solution.(1)9(2)O,o(3),O,9(4)2(5)g (b) Suppose that f(n)n g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false f(n)2~g(m)2 true false (n)=o(g(n)) true false false f(n)=6(29(m true false Solution.(a) True.(b)True. (c) False for all f, g.(d) False. Let f(n)=n, g(n) + logn� � � � � � Quiz 2 5 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the n­th harmonic number; thus, Hn = 1/1 + 1/2 + . . . + 1/n. (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) n2 log n 2 n = √ Θ O Ω o n + 1 3n − n 3 2n = Θ O Ω o 2Hn = (ln n) Θ O Ω o 0.01 n = (ln n) 100 Θ O Ω o Solution. (1) Ω (2) O, o (3) Θ, O, Ω (4) Ω (5) Ω. (b) Suppose that f(n) ∼ g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false. f(n) 2 ∼ g(n) 2 true false f(n) = O(g(n)) true false f(n) = o(g(n)) true false 2f(n) = Θ(2g(n) ) true false Solution. (a) True. (b) True. (c) False for all f, g. (d) False. Let f(n) = n, g(n) = n + log n