Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures. Note that to disprove a conjecture you only have to produce a single counterexample.
1. f(n) = O(g(n)) implies g(n) = O(f(n)).
2. f(n) + g(n) = O(min(f(n),g(n))).
3. f(n) = O(g(n)) implies 2f(n) = O(2g(n)).
4. f(n) = O(f(n/2)).
All of these conjectures are false.
1. Counterexample: f(n) = 1 and g(n) = n. It's clear that for any c, n>c*1 for n large enough.
2. Counterexample: f(n) = 1 and g(n) = n. The conjecture would imply n = O(1). Note that the similar conjecture: f(n)+g(n) = O(max(f(n),g(n))) is true.
3. Counterexample: f(n) = 2n and g(n) = n. It's clear that for any c, 4n > c2n for n large enough.
4. Counterexample: f(n) = 2n. It's clear that for any c, 4n > c2n for n large enough.