CSCI 305, Homework # 2

CSCI 305, Homework # 2

In all cases, we require that f(n) and g(n) be positive functions, i.e. f(n) 0 and g(n) 0 for all n 0. Prove or disprove each of the following conjectures.
1. f(n) = O((f(n))2)
2. f(n) = Θ(f(n/2)).
3. f(n) + o(f(n)) = Θ(f(n))
4. If f(n) = O(g(n)) then f(n) + g(n) = O(f(n)).