b igaz a c hamis

Valójában az első hamis, a másik kettő pedig igaz. Ugyanis az aszimptotikus felső korlát azt jelenti, hogy ... először vezessünk be jelöléseket, hogy lehessen hivatkozni a függvényekre:

`f(n) = O(g(n))`

Ez azt jelenti, hogy egy adott `N`-től nagyobb `n`-ek esetén `f(n) ≤ c·g(n)` ahol `c` tetszőleges konstans. Ilyen értelemben felső korlát a `g(n)`.

Először a bonyolult módszert mutatom, csak azért, mert abból lehet jobban ráérezni, hogy mi is van az egésszel:

Be kell látni, hogy van olyan `c` és `N`, amikre igaz az egyenlőtlenség, akkor igaz a feltételezés. Illetve ha be tudjuk bizonyítani, hogy nincs olyan `c` és `N`, akkor hamis.
Mondjuk a B) esetén így lehet `c`-t és `N`-et találni az igazoláshoz:
`(2n+5)^3 = 8n^3 + 60n^2+150n+ 125`
Ha `c=9`-et választunk, akkor minden olyan `n`-re, ahol `60n^2+150n+ 125 < n^3`, ott igaz lesz az, hogy `(2n+5)^3 ≤ 9·n^3`. Azt pedig behelyettesítéssel be lehet látni, hogy mondjuk `n =100`-ra már igaz a `60n^2+150n+ 125 < n^3` egyenlőtlenség, és mivel a köbös kifejezés gyorsabban nől, mint a négyzetes, azért minden nagyobb `n`-re is igaz lesz.

Ez volt a bonyolult módszer (és a végét össze is csaptam... matematikusok simán belekötnének.)

Az egyszerűbb módszer, ami az esetek nagy részében használható a bonyolultabb helyett:

Ha `lim_(n→∞) (f(n))/(g(n))` határérték létezik és véges konstans szám, akkor `g(n)` aszimptotikus felső korlát. Ha a határérték végtelen, akkor nem igaz, hogy `g(n)` felső korlát lenne.

A) `lim_(n→∞) (2^(2n+1))/(2^n)=lim_(n→∞) 2^(n+1) = ∞`, tehát nem felső korlát.
(Egyébként `4^n` felső korlát lenne.)

B) `lim_(n→∞) ((2n+5)^3)/(n^3)=8`, tehát felső korlát (aszimptotikusan persze)

C) `lim_(n→∞) (3n^2+2n+1)/(n^3)=0`, tehát felső korlát ez is.
Itt egyébként `O(n^2)` is teljesülne, vagyis van kisebb felső korlát is!!! Remélem, hogy ezt azért úgy tanultátok, hogy a nagyobb `O(n^3)` is igaz...

Megjegyés: ez a határérték teszt akkor használható, ha van határérték ami vagy véges, vagy végtelen szám. Ha nincs határérték (mert mondjuk feváltva 2 meg 3 körül kezd el konvergálni a tört), akkor nem használható, de attól még könnyen lehet, hogy (a bonyolultabb módszerrel) azt találjuk, hogy aszimptotikus felső határérték a `g(n)`.