Доказательство, что функция f (n) принадлежит Большой Тете (g (n))
Это - осуществление, которые просят указывать на класс Большая Тета (g (n)), функции принадлежат и доказать утверждение.
В этом случае f (n) = (n^2+1) ^10
По определению f (n) E Большая Тета (g (n)) <=> c1*g (n) <f (n) <c2*g (n), где c1 и c2 являются двумя константами.
Я знаю, что для этого определенного f (n) Большая Тета g (n^20), но я не знаю, кто доказать его правильно. Я предполагаю, что должен управлять этим неравенством, но я не знаю как
2 ответа
Функция f (x) равна Θ (g (x)), если и только если:
- f (x) равно O (g (x)), а
- g (x) равно O (f (x ))
Итак, хотя вы можете попытаться доказать это с помощью одного неравенства, я предлагаю вам разбить его на эти две части; сначала докажите, что для некоторого n> n 0 f (n)
Я не специалист в этом, но не могли бы вы доказать, что f(n) E Ο(n) и что f(n) E Ω(n), а затем утверждать, что f(n) E Θ(n) из-за определения пересечения?