0 Daumen
874 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community