What is the time complexity of Quick Select?

What is the time complexity of Quick Select?

Approach: Analyze selection algorithm based on partitioning.

Average case O(n). Worst case O(n^2). It is used to find the k-th smallest element in an unordered list.

Follow-up: How does it differ from Quicksort?

Key concepts: average case, worst case, partition.