Доказывая, что функция f (n) принадлежит большой тетам (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) <C2 * G (N), где C1 и C2 - две постоянные.

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

Answer 1

Функция f (x) - θ (g (x)), iff:

• f (x) o (g (x)), а также
• g (x) is o (f (x))

Итак, хотя вы можете попытаться доказать это в одном неравенстве, я предлагаю вам сломать его в эти две части; сначала докажем, что для некоторого n> n₀ f (n) <c₁ g (n), а затем доказать, что для некоторого n> n₀ g (n) <c₂ f (n). Как только вы доказали обе части, отдельно, вы можете вернуться к определению θ, чтобы доказать, что f = θ (g).

Answer 2

Я не очень эксперт на этом, но не мог бы вы доказать, что f (n) e ο (n) и что f (n) e ω (n), а затем утверждают, что f (n) e θ (n) Из-за определения пересечения?