log2 i = Theta(n log2 n).

Question

^{Hätte da diese Frage... sitze schon ziemlich lang hier und habe keine Ahnung wie ich das lösen soll...}

^{(summezeichen) bis n i = 1     log2 i = Θ(n log2 n)?}

^{Hat jemand da eine Idee ob das widerlegbar ist?}

Answer 1

$$\log1+\log2+\cdots+\log n=\log n!$$

$$\left(\frac{n}{2}\right)^{n/2}<n!<n^n$$

Comments

es ist ja log₂ i =  Θ(n * log₂ n)

hab zuerst mit induktion probiert da aber gleich bei basis nicht funktioniert denke ich dass es nicht passt oda?

wie soll man am besten widerlegen?

Lg

---

es ist ja log₂ i =  Θ(n * log₂ n)

Das ist offensichtlich falsch. In der Aufgabe steht aber eben

   log 1 + log 2 + ... + log n = Θ(n log n).

Das wuerde ich nicht widerlegen wollen. Ich wuerds lieber beweisen.

---

Danke jedenfalls für die schnelle Antwort!!

Ich habe ja wie gesagt "nur" eine Induktion aufgestellt und geschrieben dass n = 1 probiert und da sieht man sofort dass es nicht funktioniert ,würde es reichen Ihre Meinung nach für ein Beweis?

!

---

Mit der Θ-Notation macht man eine Aussage ueber das Wachstumsverhalten einer Funktion für grosse n. Was man für n=1 erhaelt ist voellig uninteressant.

Noch mal ganz langsam: Die Aussage ist richtig. Die Zutaten zum Beweis stehen in der Antwort.

---

ahh ist log(n) == log(n!)?

dann hab ich das