Asymptotic notation properties

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

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

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

3. $$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$$.

4. $$f(n) = O(g(n))$$ implies $$2^{f(n)} = O\left(2^{g(n)}\right)$$.

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

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

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

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

Although all of these can be proven or disproven mathematically, while disproving I’ll try to use counterexamples.

#### A. False

Let $$f(n) = n$$ and $$g(n) = n^2$$. $$n = O(n^2)$$ but $$n^2 \ne O(n)$$.

#### B. False

Take the same example as above. $$n^2 + n \ne \Theta(min(n^2, n)) = \Theta(min(n))$$.

#### C. True

$$f(n) = O(g(n))$$ means $$0 \le f(n) \le c \cdot g(n)$$ for all $$n \ge n_0$$ for some constants $$c, n_0 > 0$$.

Hence, $$0 \le \lg (f(n)) \le \lg c + \lg (g(n)) \le k \cdot \lg(g(n))$$.

Therefore, $$\lg (f(n)) = O(\lg(g(n)))$$.

#### D. False

Let $$f(n) = 2n$$ and $$g(n) = n$$. Hence, $$f(n) = O(g(n))$$ but $$2^{2n} = 4^n \ne O\left(2^n\right)$$.

Last part was shown in Exercise 3.1-4.

#### E. False

This conjecture holds as long as $$f(n) \ge 1$$ for sufficiently large values of $$n$$, $$0 \le f(n) \le c \cdot (f(n))^2$$, i.e. $$f(n) = O((f(n))^2)$$.

However, if $$f(n) < 1$$, this conjecture does not hold.

#### F. True

$$f(n) = O(g(n))$$ implies $$0 \le f(n) \le c \cdot g(n)$$ for all $$n \ge n_0$$ such that the constants $$c, n_0 > 0$$.

This inequality can be rearranged as $$0 \le \frac 1 c \cdot f(n) \leq g(n)$$, i.e. $$g(n) = \Omega(f(n))$$.

#### G. False

Let $$f(n) = 4^n$$. $$4^n \ne \Theta(4^{n/2}) = \Theta(2^n))$$.

#### H. True

Let’s assume $$g(n) = o(f(n))$$.

Hence, there exists positive constants $$c$$ and $$n_0$$ such that for all $$n \geq n_0$$:

$0 \leq g(n) < cf(n) \\[1ex] f(n) \leq f(n) + g(n) \leq f(n) + cf(n) \\[1ex] f(n) \leq f(n) + o(f(n)) \leq (1 + c)f(n)$

Therefore, $$f(n) + o(f(n)) = \Theta(f(n))$$.