Laufzeit: Quicksort-Verfahren mit Pivot

Question

Aufgabe:

Text erkannt:

Frage 2.c: \( \quad \) Der Median von \( n \) Zahlen lässt sich in \( O(n) \) Zeit finden. Geben Sie für ein abgewandeltes Quicksort-Verfahren, das immer den Median als Pivot-Element benutzt, die Laufzeit als Rekurrenzgleichung an und lösen Sie diese unter Zuhilfenahme des Mastertheorems! Gehen Sie davon aus, dass lauter unter-
schiedliche Zahlen eingegeben werden.

Problem:

Hallu! :-)

kann mir hier jemand helfen? Ich absolut keine Ahnung wie ich hier am besten die Laufzeit berechne...

Comments

Du brauchst überhaupt nicht am besten die Laufzeit berechnen. Es reicht wenn du auf irgendeinem mathematisch korrekten Weg die Laufzeit berechnest.

---

Aber wie soll das genau funktionieren? Wäre das hier ein Ansatz?

T(n) = 2T(n/2) + Theta(n)?