Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur Herbst 04 III-1
Bei der Aufgabe hab ich keine Ahnung was gemeint ist. Kann mir da wer helfen?
a) gemeint ist der Entscheidungsbaum für Mergesort.
(m aus m+n)
b) spezieller Fall (n aus 2n)… mit stirling kommt nan da leicht auf 2^n+1
Also ich komm da auf (2^(2n) * √(pi *n ) ) / ( p * n)
c)
Davon den Log zur Basis 2 genommen und man hat die Baumhöhe des Entscheidungsbaums, was ja der durchschnittlichen Anzahl von Vergleichen entspricht.
2n - 1/2 ld(pi * n)
Ja stimmt da kommt 2^2n raus 
wobei man bei asymptotischen Aussagen des √… des Stirling vernachlässigen kann?
c) ist richtig
Naja ich hätte gesagt, dass der Stirling ja auch nur ne Näherung ist und für große n gilt. Deswegen weiß ich nicht ob man da Teile weglassen kann und es noch weiter vergröbern kann. Wenn du bei der b) rundest, fällt dann auch bei der c) dann der ganze 1/2log(…) Käse weg. Für die O -Notations wirds reichen. Aber keine Ahnung auf was der Prüfer dann Punkte gibt und obs ihm reicht.
Hmm bei der c) hast du recht … da könnte man das sogar gebrauchen