Асимптоти c оценки и обозначение Big O

Question

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

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

Не могли бы вы дать какое-нибудь объяснение или пример, если это ложное утверждение или способ доказать, если оно правильное.

Answer 1

Я верю, что это утверждение верно. Вот доказательство.

Предположим, что f (n) = Ω (n). Это означает, что существуют константы c, n ₀ , такие что

f (n) ≥ cn для любого n ≥ n ₀ . (1)

Аналогично, поскольку f (g (n)) = O (n), мы знаем, что существуют такие константы d, n ₁ , что

f (g (n)) ≤ dn для любого n ≥ n ₁ . (2)

Теперь есть два варианта. Во-первых, g (n) = O (1), и в этом случае мы закончили, потому что тогда g (n) равно O (n). Второй случай состоит в том, что g (n) ≠ O (1), и в этом случае g растет без ограничения. Это означает, что существует n ₂ , для которого g (n ₂ ) ≥ n ₀ (g растет без ограничений, поэтому в итоге он обгоняет n ₀ ) и n ₂ ≥ n ₁ (просто выберите большое n ₂ ).

Теперь выберите любое n ≥ п ₂ . Поскольку n ≥ n ₂ , имеем g (n) ≥ g (n ₂ ) ≥ n ₀ , поскольку g монотонно возрастает, и, следовательно, ( 1) мы видим, что

f (g (n)) ≥ cg (n).

, поскольку n ≥ n ₂ ≥ n ₁ , мы можем объединить это неравенство с уравнением (2), чтобы увидеть, что

dn ≥f (g (n)) ≥ cg (n).

так, в частности, имеем, что

g (n) ≤ (d / c) n

для всех n ≥ n ₂ , поэтому g (n) = O (n).