0 Daumen
823 Aufrufe

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·2n haben soll. Nun weiß ich leider nicht, ob die Funktion in O(n·2n) oder in O(2n) ist. Ich persönlich würde eher auf O(2n) tippen, weil n nicht so stark wächst wie 2n und man deswegen den Faktor n vernachlässigen kann.

Ich wäre über eine Hilfe dankbar :)

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

Avatar von 5,7 k

Okay danke :D

Habe ich verstanden :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community