Доказательство, что если g(n) равно o(f(n)), то f(n) + g(n) есть тета (f (n))

Question

Поэтому я борюсь с доказательством (или опровержением) вышеуказанного вопроса. Я чувствую, что это правда, но я не уверен, как это показать.

Опять же, вопрос в том, что если g (n) равен o (f (n)), то f(n) + g(n) означает тета (f (n))

Обратите внимание, это мало-о, а не о-о!!!

До сих пор мне удалось (легко) показать, что:

g (n) = o (f (n)) -> g (n)

Тогда g(n) + f (n) <(c + 1) * f (n) -> (g(n) + f (n)) = O(f (n))

Однако, для показа Большой Омеги я не уверен, что там делать.

Я иду об этом правильно?

РЕДАКТИРОВАТЬ: Все оказали большую помощь, но я мог отметить только одну. БЛАГОДАРЮ ВАС.

Answer 1

Все идет нормально.

Для следующего шага напомним, что в лучшем случае 0 <= g(n); это должно дать вам нижнюю границу g(n) + f(n),

Answer 2

Один из вариантов - взять предел (f (n) + g (n)) / f (n) при стремлении n к бесконечности. Если это сходится к конечному ненулевому значению, то f(n) + g(n) = Θ(f(n)).

Предполагая, что f (n) отлично от нуля при достаточно большом n, указанное выше отношение в пределе равно

(f (n) + g (n)) / f (n)

= f (n) / f (n) + g (n) / f (n)

= 1 + g (n) / f (n).

Следовательно, принимая предел, когда n стремится к бесконечности, приведенное выше выражение сходится к 1, потому что отношение стремится к нулю (это означает, что g (n) означает o(f(n)).

Answer 3

Прежде чем мы начнем, давайте сначала отметим, что означают нотации "маленький о" и "большая тэта":

Little-o обозначение

Формально это g(n) = o(f(n)) (или же g(n) ∈ o(f(n))) имеет место для достаточно большого n означает, что для каждой положительной константы ε существует постоянная N такой, что

|g(n)| ≤ ε*|f(n)|, for all n > N                                 (+)

С https://en.wikipedia.org/wiki/Big_O_notation.

Big-Θ нотация

h(n) = Θ(f(n)) означает, что существуют положительные константы k_1, k_2 а также Nтакой, что k_1 · |f(n)| а также k_2 · |f(n)| верхняя граница и нижняя граница на |h(n)|соответственно для n > Nт.е.

k_1 · |f(n)| ≤ |h(n)| ≤ k_2 · |f(n)|, for all n > N              (++)

С https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation.

---

Дано: g(n) ∈ o(f(n))

Следовательно, в нашем случае, для каждого ε>0 мы можем найти некоторую константу N такой, что (+), для наших функций g(n) а также f(n), Следовательно, для n>N, у нас есть

|g(n)| ≤ ε*|f(n)|, for some ε>0, for all n>N

Choose a constant ε < 1 (recall, the above holds for all ε > 0), 
with accompanied constant N. 
Then the following holds for all n>N

    ε(|g(n)| + |f(n)|) ≤ 2|f(n)| ≤ 2(|g(n)| + |f(n)|) ≤ 4*|f(n)|    (*)

Снятие крайнего левого неравенства в (*) и разделив на 2, получим:

|f(n)| ≤ |g(n)| + |f(n)| ≤ 2*|f(n)|, n>N                            (**) 

Мы видим, что это само определение Big-Θ нотации, как представлено в (++)с константами k_1 = 1, k_2 = 2 а также h(n) = g(n)+f(n), следовательно

(**) => g(n) + f(n) is in Θ(f(n))

Ответ мы показали, что g(n) ∈ o(f(n)) подразумевает (g(n) + f(n)) ∈ Θ(f(n)),