0


Beweis:

Wie man die Integrale bildet ist verständlich, aber dann habe ich eine Abschätzung nach unten und eine nach oben, wie kommt man aber am Ende dann auf

n*log(n)?

Diese Frage melden
gefragt

Punkte: 47

 

Dieses Thetazeichen könnt ihr ignorieren, geht nur um nl*og(n)   ─   userf16024 06.12.2022 um 19:16
Kommentar schreiben
1 Antwort
1
Das $\Theta$ darf man eben NICHT ignorieren, weil das der ausschlaggebene Punkt ist. Es geht hier um die Landau-Symbole und da bedeutet $\Theta(n\log(n))$, dass der Ausdruck asymptotisch genauso wächst wie $n\log(n)$, was gerade NICHT bedeutet, dass der Ausdruck GLEICH $n\log(n)$ ist. Wenn die Berechnung der Integrale klar ist, musst du dir ja nur die Schranken anschauen. Die obere Schranke ist dann $n\ln(n)-n+1$, was sich asymptotisch wie $n\log(n)$ verhält, da der lineare Anteil $n+1$ asymptotisch um einiges langsamer wächst.
Diese Antwort melden
geantwortet

Selbstständig, Punkte: 30.55K

 

Kommentar schreiben