Moin moin. Unszwar geht es darum, dass man die asymptotische Notation zeigen soll, also das log2 (n!) genau so schnell wächst wie (n log2 n), bei der Fakultätsfunktion n! = n* (n-1) * (n-2)...1.
Hierzu muss in Aufgabenteil a) gezeigt werden, dass log 2 (n!) höchstens so schnell wächst wie (n log2 n) und in Aufgabenteil b), dass es mindestens so schnell wächst
Mein Ansatz. Wenn man zwei Funktionen teilt und das Ergebnis gegen unendlich geht, gilt O (höchstens so schnell). Wenn das Ergebnis gegen 0 geht, gilt Ω. Wenn das Ergebnis der Division ein konstanter Faktor ist, gilt Θ. Man könnte also log 2n! durch (n log 2n) teilen und zeigen, dass ein konstanter Faktor rauskommt und daher Θ gilt.
Die Aufgabe zwingt einen jedoch dazu, sowohl O und dann Ω zu zeigen
Ich müsste also log2n! durch (n log2 n) teilen und zeigen, dass es gegen unendlich geht, um O zu zeigen. Aber dann müsste man auch zeigen, dass es gegen 0 geht. Der Ansatz funktioniert also nicht.
Eine andere Möglichkeit wäre
log2 n! <= c * (n log2 n) zu rechnen. Aber dann müsste man auch log 2 n! >= c * (n log 2n) zeigen. Und leider kann ich n! nicht wegkürzen. :(
