Как доказать большие отношения

Question

Эй, название, вероятно, немного не так, поэтому, пожалуйста, исправьте его, если вы знаете, как лучше выразиться.

В качестве домашнего задания мне было дано несколько заданий по следующему:

Пусть f (n) и g (n) - асимптотически положительные функции. Докажите или опровергните каждую из следующих гипотез.

a. f(n) = O(g(n)) implies g(n) = O(f(n))

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

Я немного застрял, у меня записаны следующие неравенства (где <= меньше или равно) </p>

f(n) <= c1 * g(n)
g(n) <= c2 * f(n)

Но я не уверен, как бы я соединил эти 2 неравенства в одно (не) уравнение и опровергнул бы его. Я совершенно уверен, что это что-то довольно простое, что я просто упустил из виду, и что в данный момент я довольно глуп, но любые указатели / конкретные примеры того, как это сделать, было бы замечательно, так что я мог бы работать Остальные вопросы задаю сам.

Answer 1

Почему вы хотите опровергнуть это, не используя контрпример? Это самый прямой способ опровергнуть претензию.

Если бы вам пришлось доказать это, конечно, вы бы не смогли использовать контрпример. В этом случае противозачаточное средство может работать очень хорошо - предположите, что утверждение является ложным, а затем покажите, как это приводит к логическому несоответствию.

В этом случае вы начинаете с f(n) <= c1 * g(n), который является истинным, поскольку именно это означает f(n) = O(g(n)). Теперь вы хотите предположить, что g(n) <= c2 * f(n) верно для всех f и g (эта последняя часть очень важна, потому что вы, конечно, можете выбрать f и g, так что это правда), и показать, почему это не может работать. Мой совет для вас: выберите f и g таким, чтобы он не работал, и покажите, что он не может работать по вашему выбору c1 и c2.

Answer 2

Несколько подсказок:
Не забывайте, что f(n) = O(g(n)) является установленным обозначением , и вы можете преобразовать его в математическую форму неравенств.

Простые операции, которые вы можете выполнять с помощью O :

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), если c постоянная
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(Искусство компьютерного программирования, том 1 - O -Notation)