nur um sicher zu gehen, dass ich keinen Denkfehler habe:

Ein Algorithmus der eine Laufzeit von n*ln(n) hätte, sollte eigentlich schneller sein als einer der ein Laufzeit von n*log2(n) hat oder??

Hab das mit einer Rekursionsfunktion probiert zu beweisen, aber ich bekomm genau den gegenteiligen beweis raus ???

Ein Algorithmus der eine Laufzeit von n*ln(n) hätte, sollte eigentlich schneller sein als einer der ein Laufzeit von n*log2(n) hat oder??

Ja. Normalerweise hat man aber solche Laufzeiten nicht. Meistens hast du da noch additive oder multiplikative Konstanten drin. Und die können sich bei kleinem n stark auswirken.

Normalerweise hat man aber solche Laufzeiten nicht. Meistens hast du da noch additive oder multiplikative Konstanten drin. Und die können sich bei kleinem n stark auswirken.

Lass z.B. einen Bubblesort gegen Quicksort mit 5 oder 10 Elementen laufen. Meist kombiniert man verschiedene Algorithmen und nutzt entsprechend anhand der Elementzahl den günstigeren

Phil