Wie sieht denn n! aus? Du weißt natürlich, dass:
$$n! = n\cdot (n-1)\cdot\ldots\cdot1$$
Wenn du also genug Faktoren hast (wir sagen n > 3), dann hast du als Faktoren n, n-1 und irgendwelche anderen, die mindestens 3 sind.
Dann hast du mit Zusammenfassung der ersten zwei Faktoren:
$$n! = (n^2-n)\cdot(n-2)\cdot\ldots\cdot 1$$
Du kannst auch die ersten drei Faktoren zusammenfassen und hast für n > 4:
$$n! = (n^3 - 3n^2 + 2n)\cdot(n-3)\cdot\ldots\cdot1$$
Wenn du die anderen Faktoren (die du einfach mal als Koeffizienten interpretieren kannst) rausnimmst, bekommst du eine Ungleichung: n! >= n^2-n wenn n > 3, n! >= n^3 - 3n^2 - 2n wenn n > 4 usw.
Wenn du das weiter machst, dann siehst du, dass für jedes a ab n > a der Ausdruck n! mindestens so groß ist wie ein Polynom von Grad a. Daraus folgst du, dass n! asymptotisch stärker wächst als jedes Polynom.
Folglich: 2n ist in O(n!) aber nicht umgekehrt.
