Demostrando que una función f (n) pertenece a un Big-Theta (g (n))

Question

Es un ejercicio que pide que indique la clase Big-Theta (g (n)) las funciones pertenece y para demostrar la afirmación.

En este caso f (n) = (n ^ 2 + 1) ^ 10

Por definición f (n) E Big-Theta (g (n)) <=> c1 * g (n)

Yo sé que para esta específica f (n) el Big-Theta es g (n ^ 20), pero no sé que para probarlo adecuadamente. Me parece que necesito para manipular esta desigualdad, pero no sé cómo

Answer 1

Una función f (x) es T (g (x)), si y sólo si:

   
• f (x) es O (g (x)), y
   
• g (x) es O (f (x))

Así, mientras que se podría tratar de demostrar que la desigualdad en una sola, le sugiero que se descomponen en esas dos partes; primero demostrar que para algún n> n ₀ f (n) 1 g (n), y luego probar que para algunos N> N ₀ g (N) 2 f (N). Una vez que haya probado las dos partes, por separado, puede volver a la definición de T para demostrar que f = T (g).

Answer 2

No soy realmente un experto en esto, pero no podía probar que f (n) E ? (n) y que f (n) E O (n) y luego argumentar que f (n) E T (n), debido a la definición de intersección?