Blatt 4

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 4
Bei der Aufgabe 1b stimmt das sicher, dass da theta von h(n) und theta von 2^n steht… weil irgendwie kann ich nur 0(2^n) beweisen… oder hat da jemand noch nen Tip?


Die Angabe wurde gefixt :wink:


Wie sollen wir bei 2a) zwei Algorithmen vergleichen, die nur in codeform vorliegen?


Induktionbeweise sind auch mit Algorithmen möglich. Du setzt die jeweiligen Eingabewerte ein und guckst dir das Ergebnis an.
Als Hilfe hat der Lehrstuhl auch einen Induktionsbeweis für den Algorithmus für die Pascal-Zahlen online gestellt: http://www8.informatik.uni-erlangen.de/_media/ss13:kompalg:model_solution_example_blatt4.pdf