Asymptotisches Wachstum von log_2 (n!)

Question

Aufgabe:

Ordne die  folgenden  Funktionen  nach  asymptotischem  Wachstum,  beginnend  mit  deram langsamsten wachsenden Funktion.

.a) a:N→R, a(n) = 2^{log_4 n^8} log₂n

b) b:N→R, b(n) = n³ log_n6

c)c:N→R, c(n) =n³ log₅n

d)d:N→R, d(n) = \( \sum\limits_{i=1}^{n}{(\dfrac{1}{2^{i}}} \) log₂n)

e)e:N→R, e(n) = log₂(n!)

Problem/Ansatz:

a (n) lässt sich umschreiben zu (4^{log_4 (n)})⁴  = n⁴. Wächst also schon mal am schnellsten.

c (n) wächst schneller als b (n), weil bei b (n) das "n" in der Basis des Logarithmus steht, und bei c (n) das n im Logarithmus selbst.

bei d) hat unser Professor folgendes aufgeschrieben

\( \sum\limits_{i=1}^{n}{(\dfrac{1}{2^{i}}} \) log₂n) 

= log₂ n * \( \sum\limits_{i=1}^{n}{(\dfrac{1-\dfrac{1}{2^{i}}}{( \dfrac{1}{2^{i}} }} \) log2n)

= θ (log (n)

Ich verstehe nicht, was er uns hiermit sagen wollte. Klar \( \dfrac{1-\dfrac{1}{2^{i}}}{\dfrac{1}{2^{i}}} \) ist dasselbe wie 1. Aber warum macht er das? Um zu zeigen, dass es dasselbe ist wie log n?

e) Hier hab ich in meinen Notizen stehen

log₂ (n!) = \( \dfrac{n}{2}^{\dfrac{1}{2}} \) = n! = nⁿ > θ (n * log (n)

\( \dfrac{1}{2} \) n (log_n - 1) = \( \dfrac{n}{2} \) log \( \dfrac{n}{2} \) log n! ≤ n * log n

Was offensichtlich nciht sein kann, da ja n! nicht dasselbe ist wie nⁿ. Eventuell hab ich da was falsch abgeschrieben. Weiß einer, was damit gemeint sein könnte, bzw. wie ich log₂ (n!) geschickt umforme, so dass ich die Laufzeit vergleichen kann.

Comments

$$a(n)=n^4*log_2(n)$$

---

Danke. Aber ist es nicht so, dass man bei der Asymptotik das gering wachsende vernachlässigen kann? Also weil n4 ja viiiiel mehr wächst als log₂ (n), das log2 (n) dann bei der Asymptotik vernachlässigt werden kann.

Meine Frage bezog sich hauptsächtlich auf d) und e) weil ich hier die Umformungen nicht verstehe.

---

Sehen d) und e) so aus, wie du das haben wolltest?

Habe gerade aus deinen frac dfrac gemacht, damit ich die Exponenten in den Brüchen etwas besser lesen kann. Bei den Basen des log gelingt diese Verbesserung nicht so einfach.

---

Danke. Ja, genau so hab ich's gemeint.

Answer 1

d)

$$\sum_{i=1}^n{\frac{1}{2^i}\log_2n}=\log_2n\cdot\sum_{i=1}^n{\left(\frac{1}{2}\right)^i}=\theta\cdot\log_2n$$

Wobei \(\theta\) eine geometrische Reihe ist und es gilt \(\theta<1\) und \(\lim_{n\to\infty}\theta=\frac{1-\frac{1}{2}}{\frac{1}{2}}=1\)

e)

Für die Fakultät gilt folgende Abschätzung:

$$ \begin{aligned}\left(\frac{n}{2}\right)^\frac{n}{2}\quad&\le\quad n! &&\le\quad n^n \qquad\qquad |\, \log_2()\\ \frac{n}{2}\cdot\log_2\left(\frac{n}{2}\right)\quad&\le\quad \log_2(n!) &&\le\quad n\cdot\log_2(n)\\ \frac{1}{2}n\cdot\left(\log_2(n)-1\right)\quad&\le\quad \log_2(n!) &&\le\quad n\cdot\log_2(n) \end{aligned}$$