Доказательство того, что функция f (n) принадлежит Big-Theta (g (n))

Question

Это упражнение, которое просит указать класс Big-Theta (g (n)), к которому принадлежат функции, и доказать утверждение.

В этом случае f (n) = (n ^ 2 + 1) ^ 10

По определению f (n) E Big-Theta (g (n)) <=> c1 * g (n)

Я знаю, что для этого конкретного f (n) Big-Theta - это g (n ^ 20), но я не знаю, кому это доказать должным образом. Я думаю, мне нужно манипулировать этим неравенством, но я не знаю, как

Answer 1

Функция f (x) равна & gt; (g (x)), тогда и только тогда:

• f (x) означает O (г (x)) и
• г (х) - это О (ф (х))

Итак, хотя вы можете попытаться доказать это в одном неравенстве, я предлагаю вам разбить его на эти две части; сначала докажите, что для некоторых n> n ₀ f (n) 1 g (n), а затем докажите, что для некоторых N> N ₀ g (N) 2 f (N). После того, как вы проверили обе части по отдельности, вы можете вернуться к определению & Theta; доказать, что f = & theta; (g).

Answer 2

Я на самом деле не эксперт в этом, но не могли бы вы доказать, что f (n) E Ο (n) и f (n) E Ω (n), а затем утверждать, что f (n) E Θ (n) из-за определения пересечения?