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)).
