Problem 3.4

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)) \text{ implies } g(n) = O(f(n))$
2. $f(n) + g(n) = \Theta(\min(f(n), g(n)))$
3. $f(n) = O(g(n)) \text{ implies } \lg(f(n)) = O(lg(g(n))), \text{ where } \lg(g(n)) \geq 1 \text{ and } f(n) \geq 1 \text{ for all sufficiently large n}$
4. $f(n) = O(g(n)) \text{ implies } 2^{f(n)} = O(2^{g(n)}).$
5. $f(n) = O((f(n))^2)$
6. $f(n) = O(g(n)) \text{ implies } g(n) = \Omega(f(n))$
7. $f(n) = \Theta(f(n/2))$
8. $f(n) + o(f(n)) = \Theta(f(n))$

a. $f(n) = O(g(n)) \text{ implies } g(n) = O(f(n))$

Incorrect. It's easy to see that $n = O(n^2)$, but $n^2 \neq O(n)$.

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

Incorrect. Simply $n^2 + n \neq \Theta(\min(n^2, n)) = \Theta(n)$

c. $f(n) = O(g(n)) \Rightarrow \lg(f(n)) = O(lg(g(n))) \text{ if } \lg(g(n)) \geq 1, f(n) \geq 1$

Correct. We can do this, because $f(n) \geq 1$ after a certain $n \geq n_0$.

$$\exists c, n_0 : \forall n \geq n_0 : 0 \leq f(n) \leq cg(n) \\ \Downarrow \\ 0 \leq \lg{f(n)} \leq \lg(cg(n)) = \lg{c} + \lg{g(n)}$$

We need to prove that:

$$\lg{f(n)} \leq d\lg{g(n)}$$

We can easily find $d$:

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

The last step is valid, because $\lg{g(n)} \geq 1$.

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

Incorrect, because $2n = O(n)$, but $2^{2n} = 4^n \neq O(2^n)$.

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

Correct. $0 \leq f(n) \leq cf^2(n)$ is trivial when $f(n) \geq 1$.

It would be incorrect if $f(n) < 1$ for all $n$, but we are usually not interested in such functions.

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

Correct. From the first, we know that:

$$0 \leq f(n) \leq cg(n)$$

We need to prove that:

$$0 \leq df(n) \leq g(n)$$

Which is straightforward with $d = 1/c$.

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

Incorrect. Let's pick $f(n) = 2^{n}$. We will need to prove that:

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

Which is obviously untrue.

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

Correct. Let $g(n) = o(f(n))$. We need to proove that:

$$c_1f(n) \leq f(n) + g(n) \leq c_2f(n)$$

We know that:

$$\forall c \exists n_0 \forall n \geq n_0 : cg(n) < f(n)$$

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