Asymptotic notation properties proofs?

Question

I am trying to prove that if f(n) and g(n) are asymptotically positive functions, then:

1. f(n) = O((f(n))^2)

2. f(n) = O(g(n)) implies 2^(f(n)) = O(2^(g(n)))

3. f(n) = O(g(n)) implies g(n) = O(f(n))

Answer 1

1) Theorem: If f(n) is an asymptotically positive function from natural numbers to natural numbers, then f(n) = O((f(n))^2) (note I have added an extra, perhaps implied, assumption).

Proof: Because f(n) is an asymptotically positive function from natural numbers to natural numbers, it is guaranteed that for all natural numbers n greater than or equal to some natural number n0, f(n) > 0, hence f(n) >= 1. Because f(n) is guaranteed to be positive we are free to multiply both sides of the inequality by f(n) without changing the direction to get f(n)^2 >= f(n). Therefore, we can choose c = 1 and use the n0 from the assumption to show that f(n) = O((f(n))^2). (Recall that by the definition of Big-Oh, f(n) = O(g(n)) if and only if there exist constants c > 0, n0 such that for n >= n0, f(n) <= c * g(n)).

2) Theorem: if f(n) and g(n) are asymptotically positive functions from natural numbers to natural numbers and f(n) = O(g(n)), then it is not necessarily true that 2^(f(n)) = O(2^(g(n)).

Proof: The proof is by example. It can be shown that 4n = O(2n). 4n and 2n are both asymptotically positive functions from naturals to naturals. However, it can also be shown that 2^(4n) = 16^n is not O(2^(2n)) = O(4^n).

3) Theorem: if f(n) and g(n) are asymptotically positive functions from natural numbers to natural numbers and f(n) = O(g(n)), then it is not necessarily true that g(n) = O(f(n)).

Proof: The proof is by example. It can be shown that n = O(n^2). n and n^2 are both asymptotically positive functions from naturals to naturals. However, it can also be shown that n^2 is not O(n).

Answer 2

1. f(n) = O((f(n))²)

Any function is by default big-O of itself, i.e. we can use a bigger constant c_big such that f(n) <= c_big.f(n).

Thus,

• if f(n) is less than or equal to c_big.f(n),
• then f(n) will definitely be less than or equal to c_big.f(n).f(n), for asymptotically positive f(n).

Mathematically, f(n) = O(f(n).f(n)) = O(f(n)²) is true.

---

2. f(n) = O(g(n)) implies 2^f(n) = O(2^g(n))

1. f(n) = O(g(n)) implies that f(n) <= g(n)
2. Also, if some positive number n is less than m, then 2ⁿ will be less than 2^m
3. Using 1. and 2. above, we can conclude that if f(n) = O(g(n)), then 2^f(n) = O(2^g(n))

---

3. f(n) = O(g(n)) implies g(n) = O(f(n))

This one is wrong.

f(n) = O(g(n)) implies g(n) = Ω(f(n)).

If f(n) = O(g(n)), then f(n) is upper bound by g(n) which means that g(n) is lower bound by f(n), therefore g(n) = Ω(f(n)).