Результат умножения обеих сторон отношения не-большой-O на одну и ту же функцию?

Question

В целом верно ли следующее?
f∉O(g) ⇒ f*h∉O(g*h)
Где f, h, g - только положительные функции. Моя интуиция заключается в том, что это правда, но я не знаю, как это доказать.

Вот почему я думаю, что это правда:
Поскольку f∉O (g), то нет c, умноженного на g, который сделает f ≤ c * g для достаточно большого x. Не существует действительного c для g, потому что либо f и g чередуются с тем, кто находится сверху, либо f доминирует над g. Для каждого x точки f (x) и g (x) будут масштабированы на h (x), поэтому, если f (x) выше g (x), то h (x) f (x) будет выше h (х) г (х). Это будет означать, что отсутствие асимптотического доминирования должно оставаться неизменным при умножении на h, верно?

Answer 1

Предположим, что f * h равно O (g * h).Тогда существуют такие x0, c, что f (x) * h (x) <= c * g (x) * h (x) для всех x> = x0.Поскольку h всегда положительно, h (x) положительно, и мы можем делить обе части неравенства без изменения знака.Это дает f (x) <= c * g (x).Следовательно, f * h в O (g * h) подразумевает f в O (g). </p>

То, что мы только что доказали, является правдоподобным, что противоречит вашему утверждению.Ваше требование доказать:

, если f не O (g), то f * h не O (g * h)

То, что мы только что показалиis:

, если f * h равно O (g * h), то f равно O (g)

Поскольку все логические утверждения логически эквивалентны своим контрапозитивам,Ваше утверждение также верно.Вы можете рассуждать напрямую, умножая одну сторону неравенства на единицу h (x) / h (x), а затем умножая на h (x);но я думал, что отмена делением была более ясной.