Hallo sayuri,

du irrst dich .... leider reicht es nicht aus lediglich \(n=4\) einzusetzen. Theoretische reicht es auch nicht aus \(n=100\) einzusetzen. Du musst überlegen, welche Ausdrücke für sehr sehr große \(n\) größer werden als die anderen. Das geht auch gut ohne Taschenrechner. 

Sagt dir zufällig die Landau-Notation aus der theoretischen Informatik etwas? Dabei geht es zum Beispiel um die maximale Laufzeit, die ein Algorithmus braucht um im Worst-Case zu enden. Man sagt ein Algorithmus ist \(\in \mathcal{O} (n^k)\), wenn dieser eine polynomielle maximale Laufzeit hat. Beziehungsweise ist der Algorithmus \(\in \mathcal{O} (\log(n))\), wenn dieser eine logarithmische maximale Laufzeit hat. 

Der Gedanke dahinter ist wie folgt: Es werden sich Klassen von Funktionen überlegt, welche für sehr große \(n\) immer in einer Komplexitätsklasse sind. Dabei gilt folgende aufsteigende Reihenfolge für die verschiedenen Funktionsklassen:

\(a< \log(n) < \sqrt{n} <n < n\cdot \log(n) < n\cdot \log^2(n) <\ldots <n\cdot \log^k (n) < n^2 < n^2 \cdot \log(n) <n^3 < \ldots n^k < n^k \cdot \log(n) < 2^n < 3^n < \ldots <a^n <n! <n^n\)

Dabei soll \(a\) immer als beliebige Konstante stehen. Generell haben konstante Faktoren immer keinen Einfluss darauf die Klasse der Funktion zu beeinflussen. So sind \(2^n, 100 \cdot 2^n, \dfrac{1}{2021} \cdot 2^n \in \mathcal{O} (2^n)\) aber \(10\cdot 3^n \in \mathcal{O} (3^n)\). Lediglich wenn zwei Funktionen der selben Klasse angehören, wird anhand der Faktoren verglichen welche größer ist.

Jetzt würd ich dir empfehlen einige Terme noch etwas umzustellen und zu vereinfachen, damit du besser erkennen kannst welcher Komplexitätsklasse sie angehören (z.B. \(4\cdot 16^{n/2}\)). Du kannst deine Lösungen auch gerne dann noch mit hochladen und wir schauen nochmal drüber, ob deine Sortierung so stimmt.

Hier ist noch ein Link, der die Komplexitätsklassen etwas erläutert:https://www.dbs.ifi.lmu.de/Lehre/NFInfoSW/WS0708/Skript/Folien09.pdf

Hoffe ich konnte dir weiter helfen.