What is the time complexity of Quickselect?

What is the time complexity of Quickselect?

Approach: Analyze the average case of finding the k-th smallest element.

Average case O(n). Worst case O(n^2). It uses the partitioning logic of Quicksort but only recurses into one side of the partition.

Follow-up: How can you guarantee O(n) worst case? (Median of Medians)

Key concepts: O(n) average, pivot, partitioning.