Hogyan lehet bebizonyítani?

A Teta (θ) az az Ordó (O) meg Omega (Ω) párja, függvények illetve számsorozatok nagyságrendjét jellemzi.

Ha nagy x-eknél (x tart végtelen esetén) |f(x)| ≤ C·|g(x)|, ahol C lehet akármilyen nagy, de konstans kell legyen, akkor azt így jelöljük, és ordónak mondjuk:

f(x) = O(g(x))

Ez a "felülről becslés".

Az "alulról becslés" pedig így van: ha nagy x-ekre |f(x)| ≥ C·|g(x)|, akkor:

f(x) = Ω(g(x))

Ha f(x) = O(g(x)) és f(x) = Ω(g(x)) is teljesül, vagyis:

C₁·|g(x)| ≤ |f(x)| ≤ C₂·|g(x)|

akkor azt Tetának mondjuk:

f(x) = θ(g(x))

és ez azt jelenti, hogy f(x) és g(x) azonos nagyságrendű nagy x-ekre.

(Meg lehet egyébként fogalmazni a dolgot egy adott x₀ környezetre is, nem csak a végtelenre, de most az nem számít, a feladatod számsorozatnak látszik)

A bizonyítás nem bonyolult:

Majoráljuk:

a_n = 3n³ + 2n² + n + 1 ≤ 3n³+2n³+n³+n³ = 7n³ (ha n≥1)

vagyis a_n = O(n³)

Minoráljuk:

a_n = 3n³ + 2n² + n + 1 ≥ 3n³ (ha n≥1)

vagyis a_n = Ω(n³)

Mivel a_n = O(n³) valamint Ω(n³) is egyben, tehát θ(n³).