Question

More asymptotic notation. For the following questions use the definitions of O,Ω, and Θ, not our various results about them.

(a) Prove or disprove that: if f:N→R ≥0,k∈R +, and f(n)∈O(n k ), then log 2​ (f(n))∈O(log₂​ n).
(b) Prove that: if f 1​ ,f₂ :N→R ≥0 ,f 1​ ∈O(g₁ ), and f₂​ ∈O(g₂​ ), then f₁​ +f₂​∈O(max(g₁​ ,g2​ )). Here, (f₁ +f₂​ )(n)=f₁ (n)+f₂​ (n) and max(g₁​ ,g₂​ )(n)=max(g₁​ (n),g₂​ (n)).

Answer 1

(a) The statement is disproved.

If
`\(f(n) \in O(n^k)\), it does not necessarily imply that \(\log_2(f(n)) \in O(\log_2 n)\)`.

(b) The statement holds true.

If
`\(f_1(n) \in O(g_1)\) and \(f_2(n) \in O(g_2)\), then \(f_1(n) + f_2(n) \in O(\max(g_1, g_2))\)`.

Step-by-step explanation:

(a) Disproving the statement requires showcasing a counterexample. Let's assume
`\(f(n) = n^2\) and \(k = 2\). Thus, \(f(n) \in O(n^2)\). However, if we compute \(\log_2(f(n)) = \log_2(n^2) = 2\log_2(n)\). This doesn't satisfy the condition that \(\log_2(f(n)) \in O(\log_2 n)\) because \(\log_2(f(n))\)` is linear, not logarithmic. Therefore, the initial statement is disproved by showing a counterexample.

(b) To prove this statement, consider
`\(f_1(n) \in O(g_1)\) and \(f_2(n) \in O(g_2)\)`. By definition, this implies there exist constants
`\(c_1, c_2, n_1, n_2\) such that for \(n \geq n_1\), \(f_1(n) \leq c_1 \cdot g_1(n)\)`, and for
`\(n \geq n_2\), \(f_2(n) \leq c_2 \cdot g_2(n)\). Therefore, for \(n \geq \max(n_1, n_2)\), \(f_1(n) + f_2(n) \leq c_1 \cdot g_1(n) + c_2 \cdot g_2(n)\).` As
`\(c_1, c_2\) are constants and \(g_1, g_2\)` are functions, we can take
`\(c = \max(c_1, c_2)\) and \(g = \max(g_1, g_2)\)`. This allows us to conclude that
`\(f_1(n) + f_2(n) \in O(\max(g_1, g_2))\).`