Class 7 - January 27, 2025

Quicksort

• If you pick the median as a pivot, the two sides will have equal size.

• T(n) = O(n) + 2 * T(n / 2) => T(n) = O(n log(n))

• If it's sorted already, the left piece will have nothing in it, and the right has n - 1 items in it

• T(n) = O(n) + T(n - 1) => T(n) = O(n ^ 2)

• Suppose you usually pick a pivot 1/4 of the way through, then

• T(n) = O(n) + T(n * 1/4) + T(n * 3/4)

• => T(n) = O(n) + T(n * 3/4) + T(n * 3/4)

• => T(n) = O(n) + 2 * T(n * 3/4) => T(n) = O(n log n)

seelctio nsort best case o(n^2) worst O(n^2)
insertion sort best (On) worst O(n^2))