O-Kalküle: Wie erkenne ich sowas?

Question

Aufgabe:

Problem:

Hallu! (｡･∀･)ﾉﾞ

kann mir hier vielleicht jemand weiterhelfen? Und zwar würde ich gerne wissen, wie ich sowas auf die schnelle beantworten kann bzw. gleich erkenne ob z.B. f1 in O(f2) liegt und so.

Und könnte vielleicht jemand so freundlich sein und mir die Lösung angeben? Dafür bekommt derjenige auch ewige Dankbarkeit von mir. (づ￣ 3￣)づ

Answer 1

Zur Orientierung: für \(m > 1\) gilt

        \(O(1)\subset O(\log n)\subset O(n^{\frac{1}{m}})\subset O(n)\subset O(n\log n)\subset O(n^m) \subset O(2^n)\)

Comments

Hm, ich glaube, ich verstehe es nicht ganz. Heißt das einfach, wenn ich zum Beispiel f(n) = 2 log n habe, dann liegt diese Funktion in (n^m), oder?

---

Ja, es ist tatsächlich \(2 \log n \in O(n^m)\). Außerdem ist auch

        \(2\log n \in O(\log n)\).

Zur Erinnerung:

        \(f\in O(g) \iff \exists N\,\exists c>0\, \forall n\geq N\, |f(n)| \leq c\cdot|g(n)|\).

Dann sieht man \(2\log n \in O(\log n)\) durch Wahl von \(N=1,c=2\).

---

Oh, so funktioniert das also, ich Danke Dir! (o゜▽゜)o☆

Kannst Du mir vielleicht noch sagen, wie es bei den anderen noch funktioniert, also bei Θ und Ω?