Доказательство с использованием больших o и маленьких o обозначений

Question

В настоящее время я пытаюсь показать, что если g в o (f), то f не в O (g).

Я попытался определить произвольные переменные, которые доказывают, что g - это o (f) ) но я полностью застрял на том, где я должен go следующий

Answer 1

Если f ∊ O (g), это означает, что существуют константы c> 0 и N такие, что для всех n ≥ N f (n) ≤ c * g (n).

Определение для маленького o состоит в том, что если g ∊ o (f), то для каждой константы ε> 0 существует некоторое N '(не обязательно такое же, как у N выше), такое что для всех n ≥ N ', абсолютное значение | g (n) | ≤ ε * f (n).

Нам нужно показать, что если первое неравенство верно, то второе нет. Начните с перестановки первого неравенства в g (n) ≥ f (n) / c, затем выберите ε, чтобы быть некоторым числом от 0 до 1 / c. Очевидно, что следующие два не могут быть истинными для любого n, не говоря уже о всех n ≥ max (N, N '):

• g (n) ≥ f (n) / c
• | g (n) | ≤ ε * f (n)

Это прямое противоречие, поэтому отсюда следует, что f ∊ O (g) и g ∊ o (f) не могут одновременно быть правдой.