Aufgabe 2
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.
Blatt 3
Ich hab da mal ne Frage zu Blatt 3 Aufgabe 2: Wie würde man Teilaufgabe a) beweisen? Ich habe da ehrlich gesagt absolut keine Ahnung und unsere Übungsgruppe hat bei dieser Teilaufgabe auch nicht so die tolle Punktzahl erreicht.
Ich hätte das ja folgendermaßen bewiesen (sehr grob):
Da h(n) monoton und unbeschränkt ist, und unter der Annahme, dass f(n) \in O(g(n)) folgt, dass wir wegen h(n) > k zunächst schreiben können: f(k) \in O(g(k)) und somit auch f(h(n)) \in O(g(h(n)), da ja aufgrund der Monotonie die Annahme in keinster Weise verletzt wird. Dasselbe gilt dann natürlich auch für das \Omega.
Mir ist klar, dass diese Beweisführung blödsinnig ist, aber mir fällt leider nichts besseres ein. Kann mir da jemand evtl. Tipps geben bzw. eine korrekte Beweisführung zeigen? 
Die Schwierigkeit bei der Aufgabe bestand eigentlich nur darin das mathematisch korrekt auszudruecken, was ja prinzipiell schon klar ist. Ich hab mal meine Loesung angehaengt
Attachment:
main.pdf: https://fsi.cs.fau.de/unb-attachments/post_124209/main.pdf
Vielen Dank. 