Was wächst schneller?

Question

Aufgabe:

Kann mir jemand weiterhelfen, ich würde gerne wissen welche Funktion schneller wächst.

f(n) = log(n!)

g(n) = n log n

Problem/Ansatz:

Grundsätzlich weiß ich, dass n log n schneller wachsen würde als log n, da n! aber schneller wächst bin ich mir aber unsicher welche Auswirkungen das in dem oben genannten Zusammenhang hat.

Answer 1

n^n ≥ n!

für n > 1 aber bereits n^n > n!

Also nutzen wir das mal

log(n!) ≤ log(n^n) = n * log(n)

Alles klar soweit?

Comments

Danke für die Antwort! Hat mir auf jeden Fall weiter geholfen. Was ich mich allerdings noch Frage würde dann log(n!)  Element von O(n) sein ?

---

Es ist ja mehr als linear aber weniger als quadratisch also ich würde

O(n log n) für den quasi linearen Aufwand als Abschätzung nehmen.

Answer 2

hallo

log(n!)=\( \sum\limits_{k=0}^{n}{log(k)} \) damit solltest du es leicht haben. Immer an die log Gesetzt denken!

Grenzen der Summe falsch , richtig nach Hinweis von Arsinoe: log(n!)=\( \sum\limits_{k=1}^{n}{log(k)} \)

Gruß lul

Comments

log(n!)=\( \sum\limits_{k=0}^{n}{log(k)} \) ... Immer an die log Gesetzt denken!

Was ist denn log(0) ?

Answer 3

Nach Logarithmengesetzen ist f(n) = ln 1 + ln 2 + ln 3 + ... + ln(n).

Das ist die Summe von n verschiedenen Logarithmen.

Bei g(x) hat man n mal den gleichen Logarithmus ln (n), also ln(n) + ln(n) + ... +ln(n).

Da bei g(n) alle Summanden (außer dem letzten) größer sind als die Summanden von f(n) und der letzte Szummand von f(n) auch nicht größer ist als der letzte Summand von g(n), muss g(n) immer größer sein als f(n).