algorithm - f(n) = O(f(n) + g(n)) を表示していますか?

Question

次の Big-O 比較の証明は何だろうと思っていました。

f(n) は O(f(n) + g(n)))

以下を使用できることを理解しています。

f(n) ≤ 定数 * (f(n) + g(n))

しかし、フォローアップの方法がわかりません。

big-O を big-Ω に置き換えた場合はどうなるでしょうか。

Answer 1

関数 g(n) が非負であることがわかっている場合は、次のことに注意してください。

f(n) ≤ f(n) + g(n) = 1 · (f(n) + g(n))

これを踏まえて、f(n) = O(f(n) + g(n)) を示すために big-O 表記の正式な定義を使用できますか?

g(n) が必ずしも非負でない場合、この結果は必ずしも true ではありません。たとえば、f(n) = n および g(n) = -n を取ります。次に、f(n) + g(n) = 0 であり、f(n) = O(0) は正しくありません。

Ω の場合についてですが、この結果は必ず正しいと思いますか? ヒントとして、f(n) = n と g(n) = 2 ⁿを選んでみてください。ここで f(n) は本当に Ω(f(n) + g(n)) ですか?

お役に立てれば！