Ce qui prouve que la fonction f (n) appartient à un Big-Theta (g (n))

Question

L'un exercice qui demande pour indiquer la classe Big-Theta (g (n)) les fonctions appartient et de prouver l'affirmation.

Dans ce cas, f (n) = (n ^ 2 + 1) ^ 10

Par définition f (n) E Big-Theta (g (n)) <=> c1 * g (n)

Je sais que pour cette f spécifique (n) le Big-Theta est g (n ^ 20), mais je ne sais pas qui de prouver correctement. Je suppose que je dois manipuler cette inégalité, mais je ne sais pas comment

Answer 1

Une fonction f (x) est T (g (x)), si et seulement si:

   
• f (x) est O (g (x)), et
   
• g (x) est O (f (x))

Ainsi, alors que vous pourriez essayer de le prouver en une seule inégalité, je vous suggère de le décomposer en ces deux parties; d'abord prouver que, pour une n> n ₀ f (n) 1 g (n), puis prouver que pour certains N> N ₀ g (N) 2 f (N). Une fois que vous avez prouvé les deux parties, séparément, vous pouvez revenir à la définition de T pour prouver que f = T (g).

Answer 2

Je ne suis pas un expert, mais ne pourrais pas vous prouver que f (n) E ? (n) et que f (n) E O (n), puis faire valoir que f (n) E T (n) en raison de la définition d'intersection?