Vergleiche Wachstum mithilfe landau notation

Question

Aufgabe:

Gegeben seien die FKT

x^3, log(x), 2^x, x^2, x^3+1000x^2 , e^x

Vergleichen Sie das Wachstum dieser Funktion für x-> unendlich und x-> 0 mit hilfe der Landau- Notation

Problem/Ansatz:

Ich weiß bei x-> unendlich

für x^2 wächst quadratisch

2^x wächst exponetiell

log(x) wächst logarithmisch

witer weiß ich nicht wie ich das vergleichen soll

Answer 1

Aloha :)

Wir sollen die asymptotischen Laufzeiten mit Hilfe der Landau-Notation vergleichen.$$\log(x)\in O(\log(x))$$$$x^2\in O(x^2)$$$$x^3\in O(x^3)$$$$x^3+1000x^2\in O(x^3)\quad\text{denn: }\lim\limits_{x\to\infty}\frac{x^3+1000x^2}{x^3}=\lim\limits_{x\to\infty}\left(1+\frac{1000}{x}\right)=1<\infty$$$$2^x\in O(2^x)$$$$e^x\red{\not\in} O(2^x)\quad\text{denn: }\lim\limits_{x\to\infty}\frac{e^x}{2^x}=\lim\limits_{x\to\infty}\left(\frac e2\right)^x=\infty$$$$e^x\in O(e^x)$$

\(x^3\) und \((x^3+1000x^2)\) haben dieselbe asymptotische Laufzeit \(O(x^3)\).

\(e^x\in O(e^x)\) wächst asymptotisch schneller als \(2^x\in O(2^x)\).