Asymptotic notation properties
Let \(f(n)\) and \(g(n)\) be asymptotically positive functions. Prove or disprove each of the following conjectures.
\(f(n) = O(g(n))\) implies \(g(n) = O(f(n))\).
\(f(n) + g(n) = \Theta(min(f(n), g(n)))\).
\(f(n) = O(g(n))\) implies \(\lg (f(n)) = O(\lg(g(n)))\), where \(\lg(g(n)) \ge 1\) and \(f(n) \ge 1\) for all sufficiently large \(n\).
\(f(n) = O(g(n))\) implies \(2^{f(n)} = O\left(2^{g(n)}\right)\).
\(f(n) = O((f(n))^2)\).
\(f(n) = O(g(n))\) implies \(g(n) = \Omega(f(n))\).
\(f(n) = \Theta(f(n/2))\).
\(f(n) + o(f(n)) = \Theta(f(n))\).
Although all of these can be proven or disproven mathematically, while disproving I’ll try to use counterexamples.
A. False
Let \(f(n) = n\) and \(g(n) = n^2\). \(n = O(n^2)\) but \(n^2 \ne O(n)\).
B. False
Take the same example as above. \(n^2 + n \ne \Theta(min(n^2, n)) = \Theta(min(n))\).
C. True
\(f(n) = O(g(n))\) means \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\) for some constants \(c, n_0 > 0\).
Hence, \(0 \le \lg (f(n)) \le \lg c + \lg (g(n)) \le k \cdot \lg(g(n))\).
Therefore, \(\lg (f(n)) = O(\lg(g(n)))\).
D. False
Let \(f(n) = 2n\) and \(g(n) = n\). Hence, \(f(n) = O(g(n))\) but \(2^{2n} = 4^n \ne O\left(2^n\right)\).
Last part was shown in Exercise 3.1-4.
E. False
This conjecture holds as long as \(f(n) \ge 1\) for sufficiently large values of \(n\), \(0 \le f(n) \le c \cdot (f(n))^2\), i.e. \(f(n) = O((f(n))^2)\).
However, if \(f(n) < 1\), this conjecture does not hold.
F. True
\(f(n) = O(g(n))\) implies \(0 \le f(n) \le c \cdot g(n)\) for all \(n \ge n_0\) such that the constants \(c, n_0 > 0\).
This inequality can be rearranged as \(0 \le \frac 1 c \cdot f(n) \leq g(n)\), i.e. \(g(n) = \Omega(f(n))\).
G. False
Let \(f(n) = 4^n\). \(4^n \ne \Theta(4^{n/2}) = \Theta(2^n))\).
H. True
Let’s assume \(g(n) = o(f(n))\).
Hence, there exists positive constants \(c\) and \(n_0\) such that for all \(n \geq n_0\):
\[0 \leq g(n) < cf(n) \\[1ex] f(n) \leq f(n) + g(n) \leq f(n) + cf(n) \\[1ex] f(n) \leq f(n) + o(f(n)) \leq (1 + c)f(n)\]Therefore, \(f(n) + o(f(n)) = \Theta(f(n))\).