Let \(f(n)\) and \(g(n)\) be asymptoticaly positive functions. Prove or disprove each of the following conjectures.

a. \(f(n) = O(g(n)) \implies g(n) = O(f(n))\).

Let \(f(n) = n^2\) and \(g(n) = n^3\). \(n^2 = O(n^3)\), but \(n^3 \neq O(n^2)\) which proves this conjecture is false.

b. \(f(n) + g(n) = \Theta(\min(f(n), g(n)))\).

Let \(f(n) = n^2\) and \(g(n) = 0\). \(\min(f(n), g(n)) = 0 \ \forall n\). \(n^2 \neq \Theta(0)\) which proves this conjecture is false.

c. \(f(n) = O(g(n)) \implies \lg(f(n)) = O(\lg(g(n)))\), where \(\lg(g(n)) \geq 1\) and \(f(n) \geq 1\) for all sufficiently large \(n\).

\(f(n) = O(g(n))\) means that there exist some positive constants \(c\) and \(n_0\) such that \(0 \leq f(n) \leq c \cdot g(n) \ \forall \ n > n_0\). To prove this conjecture, we must show that there exist some positive constants \(c_1\) and \(n_1\) such that \(0 \leq \lg(f(n)) \leq c_1 \cdot \lg(g(n)) \ \forall \ n > n_1\). Applying a logarithm to both our functions indicates that our constants may change, but it has not changed the asymptotic properties of each function. Because the conjecture allows for sufficiently large values of \(n\) (thus enabling us to choose a \(n_1\) that is likely larger than \(n_0\)) and because \(f(n) \geq 1 \implies \lg(f(n)) \geq 0\) and \(\lg(g(n)) \geq 1 \geq 0\) we conclude that our inequality holds which proves this conjecture is true.

d. \(f(n) = O(g(n)) \implies 2^{f(n)} = O(2^{g(n)})\).

Let \(f(n) = 2n\) and \(g(n) = n\). \(2n = O(n)\), but \(2^{f(n)} = 2^{2n} = 4^n \neq O(2^{g(n)}) = O(2^n)\) which proves this conjecture is false.

e.\(f(n) = O((f(n))^2)\).

By reflexivity we know that \(f(n) = O(f(n))\). \(f(n)^2 \geq f(n)\) holds for all values of \(f(n)\) that are not less than \(1\) which means this conjecture holds except for the subset of functions \(f'(n)\) such that \(f'(n) < 1 \ \forall \ n\).

f.\(f(n) = O(g(n)) \implies g(n) = \Omega(f(n))\).

We know this to be true based on transpose symmetry. However to formally prove, \(f(n) = O(g(n))\) means there exist some constants \(c\), \(n_0\) such that \(0 \leq f(n) \leq c \cdot g(n) \ \forall \ n > n_0\). \(g(n) = \Omega(f(n))\) means there exist some constants \(d\), \(n_1\) such that \(0 \leq d \cdot f(n) \leq g(n) \ \forall \ n \geq n_1\). We can obtain the 2nd inequality from the first by dividing both sides by \(d\). This means that this inequality holds when we choose \(c = \frac{1}{d}\) and \(n_0 = n_1\) which proves this conjecture is true.

g.\(f(n) = \Theta(f(n/2))\).

Let \(f(n) = 2^n\). Then \(f(n/2) = 2^{n/2}\). \(2^n = \Theta(2^{n/2})\) means that there exist positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(0 \leq c_1 \cdot 2^{n/2} \leq 2^n \leq c_2 \cdot 2^{n/2} \ \forall \ n > n_0\). This inequality cannot be satisfied which proves this conjecture is false.

h.\(f(n) + o(f(n)) = \Theta(f(n))\).

This conjecture is stating that there exist positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(0 \leq c_1 \cdot f(n) \leq f(n) + o(f(n)) \leq c_2 \cdot f(n) \ \forall \ n > n_0\). By definition, \(o(f(n))\) is ‘less than’ \(f(n)\), therefore this inequality holds when we select \(c_1 = 1\) and \(c_2 = 2\) and \(n_0\) as the value for which \(o(f(n))\) is valid. Therefore this conjecture is true.