Aufwandsabschätzung einer Funktion im groß O-Kalkül/O-Notation

Question

Hallo :)

Ich soll bei einer Funktion den Aufwand im groß O-Kalkül/O-Notation abschätzen. Und zwar bin ich auf das Ergebnis gekommen, dass die Funktion bei n Eingaben einen "Aufwand" von n·2ⁿ haben soll. Nun weiß ich leider nicht, ob die Funktion in O(n·2ⁿ) oder in O(2ⁿ) ist. Ich persönlich würde eher auf O(2ⁿ) tippen, weil n nicht so stark wächst wie 2ⁿ und man deswegen den Faktor n vernachlässigen kann.

Ich wäre über eine Hilfe dankbar :)

Answer 1

Damit n·2ⁿ∈O(2ⁿ) ist müsste es ein c geben,so dass für hinreichend große n die Ungleichug n·2ⁿ ≤ c·2ⁿ gilt. Spätestens wenn dann n>c ist gilt diese Ungleichung aber nicht mehr. Deshalb ist O(2ⁿ) ≠ O(n·2ⁿ).

Comments

Okay danke :D

Habe ich verstanden :)