Aufgabe (inkl. Lösung):
Geben Sie jeweils eine Funktion f an, welche die angegebenen Wachstumseinschränkungen einhält.
f ∈ ω(√n) f ∈ o(n) Lösung :f(n) = ³√n2
f ∈ ω(n) f ∈ o(n log n) Lösung: f(n) = n log log n
4f ∈ Θ(2f) Lösung: f(n) = 1
f ∈ Θ(n) f ∈ o(2n) Lösung: f(n) = (1/2)n
Problem:
Ich verstehe leider nicht, auf welche Art und Weise, die Funktionen bestimmt/berechnet wurden. Mit der Landau/O-Notation kenne ich mich aus, allerdings kann ich die Lösung zwar einigermaßen nachvollziehen (die Ergebnisse sind auch soweit richtig), allerdings könnte ich diese nicht eigenständig replizieren bzw. wüsste nicht, wie ich auf jene kommen könnte. Habt ihr eine Idee?