I am trying to prove that if f(n) and g(n) are asymptotically positive functions, then:
f(n) = O((f(n))^2)
f(n) = O(g(n)) implies 2^(f(n)) = O(2^(g(n)))
f(n) = O(g(n)) implies g(n) = O(f(n))
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).