Bevis: Stor O notasjon

[Nebuchadnezzar]

Jobber litt med noen bevis angående stor O-notasjon, og erlitt usikker.
Leste påsten til svinepelz her, og den gjorde meg litt usikker. Spesielt svaret til Espen.

http://www.matematikk.net/ressurser/mat ... hp?t=31193

Jeg ønsker å bevise atnår [tex]x \to 0[/tex] så er [tex]x^m = \mathcal{O}(x^n)[/tex] der [tex]m>n[/tex]

Nå er jo dette ganske åpenbart... Når x går mot null, oppfører jo disse funksjonene seg på samme måte.

Utifra posten ovenfor så er dette det samme som å bevise at

[tex]\lim_{x \to 0} \left| \frac{x^m}{x^n}\right| \ < \ \infty[/tex]

Stemmer dette ? Da kan jeg jo skrive at

[tex]L = \lim_{x \to 0} \left| \frac{x^m}{x^n}\right|[/tex]

[tex]L = \lim_{x \to 0} \left| x^{m-n} \right|[/tex]

[tex]L = 0[/tex]

Men igjen er dette noe fullg godt bevis? Og er det riktig?

Den definisjonen virker veldig åpen, og litt absurd. Da kan en jo nesten vise alt via den grenseverdien...

[Per Spelemann]

Ja, tror det vil være nok å vise at

[tex]\lim_{x \to 0} \left| \frac{x^m}{x^n} \right| < \infty[/tex]

Da vil vel nemlig også tilsvarende «lim sup»-uttrykk være mindre enn uendelig.

Når x går mot null, oppfører jo disse funksjonene seg på samme måte.

Helt likt oppfører de seg ikke, den ene vil gå kjappere mot null enn den andre.
Hva vil skje dersom [tex]m < n[/tex]?

[Nebuchadnezzar]

Uendelig!

[svinepels]

Du kan også bevise det direkte med definisjonen av store O (tror det var det de fleste gjorde på øvinga). Da trenger du bare å finne [tex]\epsilon>0[/tex] og [tex]K>0[/tex] slik at

[tex]|x| < \epsilon \; \Rightarrow \; |x^m| \leq K |x^n|[/tex]

Ser du hvilke epsilon og K du kan velge? Faktisk er det to tall som gjør uttrykkene veldig pene. Husk på at m >= n!

[Nebuchadnezzar]

Nå er jeg sikker heeelt på viddene. Burde lære meg dett skikkelig snart

Men [tex]1/\epsilon[/tex] og [tex]K =1[/tex] ?

[svinepels]

Hvis du velger epsilon = 1 og K = 1, hva skjer da? =)