Subato
(Algorithmen und Datenstrukturen SS 2022)
Exercise Sheet 3
Asymptotische Notationen
Due Date: 2022-05-11 23:59:00.0
Auf diesem Übungsblatt werden wir uns hauptsächlich mit asymptotischen Notationen beschäftigen. Diese dienen in der Informatik für die Beurteilung von Algorithmen und werden u.a. zur groben Abschätzung der Laufzeit von Algorithmen eingesetzt.
Diesmal müssen Sie nicht programmieren, sondern rechnen und kleine Beweise führen. Die Abgabeform ist also ein sauber geschriebenes (handschriftlich!) und gescanntes PDF! Maschinelle Formate (Word, Text, LaTeX etc.) sind nicht zulässig.
-
Exercise 1
Mathe-Grundlagen
Wichtige Grundlagen aus "Analysis" und "Diskrete Strukturen".
-
Exercise 2
O-Notation I
Beweise zur O-Notation
-
Exercise 3
Code-Komplexität
Bestimmen Sie die Komplexitätsklasse von Code-Stücken.