3-4 Asymptotic notation properties

Let $f(n)$ and $g(n)$ by asymptotically positive functions. Prove or disprove each of the following conjectures.

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

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

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

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

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

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

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

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

a. Disprove, $n = O(n^2)$, but $n^2 \ne O(n)$.

b. Disprove, $n^2 + n \ne \Theta(\min(n^2, n)) = \Theta(n)$.

c. Prove, because $f(n) \ge 1$ after a certain $n \ge n_0$.

$$ \begin{aligned} \exists c, n_0: \forall n \ge n_0, 0 \le f(n) \le cg(n) \\ \Rightarrow 0 \le \lg f(n) \le \lg (cg(n)) = \lg c + \lg g(n). \end{aligned} $$

We need to prove that

$$\lg f(n) \le d\lg g(n).$$

We can find $d$,

$$d = \frac{\lg c + \lg g(n)}{\lg g(n)} = \frac{\lg c}{\lg g(n)} + 1 \le \lg c + 1,$$

where the last step is valid, because $\lg g(n) \ge 1$.

d. Disprove, because $2n = O(n)$, but $2^{2n} = 4^n \ne O(2^n)$.

e. Prove, $0 \le f(n) \le cf^2(n)$ is trivial when $f(n) \ge 1$, but if $f(n) < 1$ for all $n$, it's not correct. However, we don't care this case.

f. Prove, from the first, we know that $0 \le f(n) \le cg(n)$ and we need to prove that $0 \le df(n) \le g(n)$, which is straightforward with $d = 1 / c$.

g. Disprove, let's pick $f(n) = 2^n$. We will need to prove that

$$\exists c_1, c_2, n_0: \forall n \ge n_0, 0 \le c_1 \cdot 2^{n / 2} \le 2^n \le c_2 \cdot 2^{n / 2},$$

which is obviously untrue.

h. Prove, let $g(n) = o(f(n))$. Then

$$\exists c, n_0: \forall n \ge n_0, 0 \le g(n) < cf(n).$$

We need to prove that

$$\exists c_1, c_2, n_0: \forall n \ge n_0, 0 \le c_1f(n) \le f(n) + g(n) \le c_2f(n).$$

Thus, if we pick $c_1 = 1$ and $c_2 = c + 1$, it holds.