Ich Studiere im ersten Semester Informatik und habe heute diese Aufgabe bekommen:
a) Sortieren Sie für die unten angegebenen Funktionen die O-Klassen \( O(a(n)), O(b(n)), O(c(n)), O(d(n)) \) und \( O(e(n)) \) bzgl. ihrer Teilmengenbeziehung. Nutzen Sie ausschlieflichen \( n^{\prime \prime \prime} \) und \( n=" \) für die Beziehungen zwischen den Mengen. \( \left(\right. \) Notationsbeispiel: \( \left.O\left(f_{1}(n)\right) \subset O\left(f_{2}(n)\right)=O\left(f_{3}(n)\right) \subset O\left(f_{4}(n)\right)=O\left(f_{5}(n)\right)\right) \)
\( a(n)=n^{2} \log _{2} n+42 \quad b(n)=2^{n}+n^{4} \quad c(n)=2^{2 n} \quad d(n)=2^{n+3} \quad e(n)=\sqrt{n^{5}} \)
b) Beweisen \( \operatorname{Sie}\left(\log _{2} n\right)^{2} \in O(n) \)
c) Beweisen Sie \( n ! \in \Omega\left(3^{n}\right) \)
d) Beweisen Sie \( \sum \limits_{k=1}^{n} k^{7} \in O\left(n^{8}\right) \)
Wie ihr seht, handelt es sich ja dabei um die O Notation...doch wie sollen denn die Beweise aussehen?
Ich würde den Rechenweg wirklich gerne nachvollziehen.In der Übung gab es keinen Hinweis auf die Aufgabe.