MATH-2221 Lecture 25: 4.8 cont

( computer answer ) not paper

3. Prove or disprove (formally) the following:

(a) n log2 n ∈ O(2n 1/3 ).

(b) log(5n) ∈ O(log(2n)).

(c) 2 2 n+1 ∈ O(22 n ).

(d) [f1(n) ∈ O(g1(n)) ∧ f2(n) ∈ O(g2(n))] ⇐⇒ [f1(n) + f2(n) ∈ O(g1(n) + g2(n))].