Dimostrando che una funzione f (n) appartiene un Big-Theta (g (n))

Question

E 'un esercizio che chiede di indicare la classe di Big-Theta (g (n)) le funzioni di appartenenza e per dimostrare l'affermazione.

In questo caso f (n) = (n ^ 2 + 1) ^ 10

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

So che per questo specifico f (n) il Big-Theta è g (n ^ 20), ma non so chi per dimostrare in modo corretto. Credo che ho bisogno di manipolare questa disuguaglianza, ma io non so come

Answer 1

Una funzione f (x) è T (g (x)), se e solo se:

   
• f (x) è O (g (x)), e
   
• g (x) è O (f (x))

Così, mentre si potrebbe provare a dimostrarlo in un unico disuguaglianza, vi consiglio di scomposizione in quei due parti; prima dimostrare che per qualche n> n ₀ f (n) 1 g (n), e quindi dimostrare che per qualche n> N ₀ g (N) 2 f (N). Una volta che avete provato entrambe le parti, separatamente, è possibile tornare alla definizione di T per dimostrare che f = T (g).

Answer 2

In realtà non sono un esperto in questo, ma non si potrebbe dimostrare che f (n) E ? (n) e che f (n) E O (n) e poi sostenere che f (n) E T (n) a causa della definizione di intersezione?