TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 1

Zeigen Sie, dass $10^{n}=O(n!)$ gilt, indem sie konkrete Werte für $n_{0}$ und c finden und beweisen, dass die entsprechenden Ungleichungen mit diesen Konstanten erfüllt werden können.

Lösung

Aus der Überlegung dass $10^{n}=10*10*10...$ ist und $n!=1*2*3*4*...$ ist muss das asympthotische Verhalten von n! entsprechend größer sein als $10^{n}$.

Beweis durch wählen von einem gewissen Wert (z.B. n=30): $30!=2,6525*10^{32}>10^{30}$

Überlegung

Ab dem Wert 11 wächst die Permutation schneller als die Exponentialfunktion. Dh. der "Vorsprung" wird irgendwann eingeholt (bei 28). Andersrum könnte man das ganze auch mathematisch untermauern indem man für n! die Stirling-Näherungsformel einsetzt:

$n!\approx {\sqrt {2*\pi *n}}*({\frac {n}{e}})^{n}$

Nach einem Umformen wird man erkennen, dass ab n=10 die Permutation schneller wächst als die Exp.-Funktion. Was auch der einfachen Überlegung von vorhin entspricht.