3-4 Asymptotic notation properties

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

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

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

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

d. \(f(n) = O(g(n))\) implies \(2^{f(n)} = O(2^{g(n)})\).

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

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

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

h. \(f(n) + o(f(n)) = \Theta(f(n))\).

a. Disprove, \(n = O(n^2)\), but \(n^2 \ne O(n)\).

b. Disprove, \(n^2 + n \ne \Theta(\min(n^2, n)) = \Theta(n)\).

c. Prove, because \(f(n) \ge 1\) after a certain \(n \ge n_0\).

We need to prove that

We can find \(d\),

where the last step is valid, because \(\lg g(n) \ge 1\).

d. Disprove, because \(2n = O(n)\), but \(2^{2n} = 4^n \ne O(2^n)\).

e. Prove, \(0 \le f(n) \le cf^2(n)\) is trivial when \(f(n) \ge 1\), but if \(f(n) < 1\) for all \(n\), it's not correct. However, we don't care this case.

f. Prove, from the first, we know that \(0 \le f(n) \le cg(n)\) and we need to prove that \(0 \le df(n) \le g(n)\), which is straightforward with \(d = 1 / c\).

g. Disprove, let's pick \(f(n) = 2^n\). We will need to prove that

which is obviously untrue.

h. Prove, let \(g(n) = o(f(n))\). Then

We need to prove that

Thus, if we pick \(c_1 = 1\) and \(c_2 = c + 1\), it holds.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用