Asymptotic notation properties

Let \(f(n)\) and \(g(n)\) be asymptotically positive functions. Prove or disprove each of the following conjectures.

  1. \(f(n) = O(g(n))\) implies \(g(n) = O(f(n))\).

  2. \(f(n) + g(n) = \Theta(min(f(n), g(n)))\).

  3. \(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\).

  4. \(f(n) = O(g(n))\) implies \(2^{f(n)} = O\left(2^{g(n)}\right)\).

  5. \(f(n) = O((f(n))^2)\).

  6. \(f(n) = O(g(n))\) implies \(g(n) = \Omega(f(n))\).

  7. \(f(n) = \Theta(f(n/2))\).

  8. \(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))\).