Oppgaver i diskret matematikk

[Mehe]

Jeg forstår fint lite av denne oppgaven, håper noen kan hjelpe meg:

- Vis at hvis f(x) og g(x) er funksjoner fra R -> R, så vil f(x) være stor Theta av g(x) hvis og bare hvis det finnes positive konstanter C1, k1, C2 og k2 slik at C1|g(x)| er mindre eller lik |f(x)| mindre eller lik C2|g(x)| når x > k.

- Vis at 3x^2 + x + 1 er stor Theta av 3x^2 ved å direkte finne konstantene k, C1 og C2 i oppgaven over.

[Solar Plexsus]

Her har vi at

[tex]3x^2 \;<\; 3x^2 \:+\: x \:+\: 1 \;<\; 2 \cdot (3x^2)[/tex]

for alle [tex]x \, > \, 1[/tex]. Så ved å velge og C[sub]2[/sub] = 2 og C[sub]1[/sub] = k = 1, vil funksjonen [tex]3x^2 \:+\: x \:+\: 1[/tex] være "stor Theta" av [tex]3x^2[/tex].