Функции f не в O (g) и g не в O (f)

Question

Вопрос в следующем:

Показать или опровергнуть, что для двух функций f, g, если f не в O (g), то g в O (f).

Мой контрпример:

Let f(n) be   f(n) = n^2 : if n is even
                  or n^4 : if n is odd

Let g(n) be   g(n) = n^3

Это пример для f не в O (g) и g не в O (f). Мой пример неверен? Если так, то почему? У вас есть другие примеры?

Answer 1

Ваш контрпример работает. Доказательство может выглядеть так:

Предположим, что f были O (g). Тогда существует положительная постоянная c и n0, такие что для n> = n0, f (n) <= c * g (n). Пусть n 'будет нечетным целым числом, большим или равным n0. Тогда мы имеем n '^ 4 <= c * n' ^ 3. Разделив обе стороны на n '^ 3, мы получим n' <= c. Однако это не может быть правдой для всех n '> n0; таким образом, есть даже n больше чем n0, для которых условие не выполняется, противоречие.

Доказательство наоборот - аналогично, за исключением того, что вы делите обе стороны на n '^ 2.

Я думаю, что контрпример, который вы определили, является хорошим для этого; функция, которая колеблется на асимптотически возрастающей величине, и функция, которая идет где-то посередине.