Beweis für Laufzeit nlogn

[Odi1981]

Wie kann ich beweisen, das ein Algorithmus wie QuickSort oder MergeSort nicht schneller als nlogn arbeiten kann ??

Danke Odi

[setiII]

QuickSort

Na ja anhand des Programmablaufes stellst du einfach die Zeitkomplexität auf.

Für den ist es

(n log(n)) im Durchschnitt und

(n2) im schlechtesten Fall

Nu ja und jetzt musst du nur noch zeigen das dies immer schlechter ist als deins sein kann. (was aber eben nur im Mittel stimmt, und im optimum eben schon)

Wenn du nicht weist was o(n) ist, ....