3-4 Asymptotic notation properties

Let $f(n)$ and $g(n)$ be 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)\geq 1$ and $f(n)\geq 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\neq O(n)$

b

Disprove:$n+n^2\neq \Theta(\min(n,n^2))$

c

prove:

$$ \begin{aligned} 0\leq f(n)\leq cg(n) & \implies \lg(f(n))\leq \lg c+\lg(g(n))\cr \text{to prove: }&\lg(f(n)) \leq d\lg(g(n))\cr \text{only need to prove: }& \lg c + \lg(g(n)) \leq d\lg(g(n))\cr \text{choose } & \quad d = 1+\lg c \text{ satisfies} \end{aligned} $$

d

prove:

$$ \begin{aligned} 0\leq f(n)\leq cg(n) \implies 2^{f(n)}\leq 2^{cg(n)}=2^c\cdot c^{g(n) } \end{aligned} $$

e

disprove: $\frac{1}{n}\neq O(\frac{1}{n^2})$

f

prove: $0\leq f(n)\leq cg(n) \implies g(n)=\Omega (f(n))$

g

disprove:$2^n\neq\Theta(2^{\frac{n}{2}})$

h

prove: $f(n)\leq f(n)+o(f(n))\leq 2f(n)$ since $0\leq o(f(n))< f(n)$