Асимптотический рост: Понимание конкретного доказательства f (n) + little o (f (n)) = theta (f (n))?

Question

Я работаю через доказательство f(n) + o(f(n)) = theta (f(n)), и я наткнулся на часть в доказательстве, что у меня проблемы с пониманием.

Мы допускаем асимптотически положительные функции f(n) и g(n) и принимаем g(n) = O(f(n)).В доказательстве говорится, что, поскольку мы знаем, что f(n) + g(n) ≥ f(n) для всех n, мы можем заключить, что f(n) + g(n) = Omega((f(n)).Мы также можем сделать аналогичный вывод, что f(n) + g(n) ≤ 2 f(n).Поэтому f(n) + g(n) = O(f(n)).У меня проблемы с пониманием того, почему f(n) + g(n) = Omega((f(n)) и f(n) + g(n) = O(f(n)) были бы правдой.Как получается, что мы можем доказать, что жесткая нижняя граница предназначена именно тогда, когда мы добавляем g(n) к f(n)?Что именно мы делаем вывод из значения g(n)?

Answer 1

Один из способов доказать, что f(n) - это theta(g(n)), - это доказать два отдельных утверждения: f(n) - это omega(g(n)), а f(n) - это O(g(n)).Ясно, что этот способ доказательства верен из определений этих обозначений.

В этой точной задаче, если мы выберем некоторую константу c равную 1, мы будем иметь для каждого n, что f(n) + g(n) >= c * f(n), так что, по определению, показывает, чтоf(n) + g(n) - это Omega(f(n)).Кроме того, для части O(f(n)), если мы выберем в этом случае постоянную c равную 2, нам нужно доказать, что существует некоторая n0 такая, что f(n) + g(n) <= c * f(n) для каждого n > n0, чтоэквивалентно g(n) <= f(n) для каждого n > n0, что эквивалентно определению g(n) = O(f(n)), данному в постановке задачи.

Надеюсь, это поможет.