Der Beweis, dass eine Funktion f (n) gehört zu einem Big-Theta (g (n))

Question

Es ist eine Übung, die die Klasse Big-Theta (g (n)), um die Funktionen, um anzuzeigen, fragt gehört, und die Behauptung zu beweisen.

In diesem Fall ist f (n) = (n ^ 2 + 1) ^ 10

Per Definition f (n) E Big-Theta (g (n)) <=> c1 * g (n)

Ich weiß, dass für diesen speziellen f (n) der Big-Theta ist g (n ^ 20), aber ich weiß nicht, wer es richtig zu beweisen. Ich glaube, ich brauche diese Ungleichheit zu manipulieren, aber ich weiß nicht, wie

Answer 1

Eine Funktion f (x) ist, T (g (x)), genau dann, wenn:

• f (x) O (g (x)) und
• g (x) O (f (x))

So, während Sie versuchen, es könnte in einer einzigen Ungleichheit zu beweisen, ich schlage vor, Sie brechen sie in diesen zwei Teile; erste beweisen, dass für einige n> n ₀ f (n) 1 g (n) und dann nachweisen, dass für einige N> N ₀ g (N) 2 f (N). Sobald Sie beiden Teile unter Beweis gestellt haben, getrennt, können Sie auf die Definition von T gehen zurück zu, dass f zu beweisen = T (g).

Answer 2

Ich bin nicht wirklich ein Experte auf diesem, aber könnten Sie beweisen nicht, dass f (n) E ? (n) und f (n) E O (n) und argumentiert dann, dass f (n) E T (n) aufgrund der Definition der Kreuzung?