Consider the task of finding the kth smallest value from an array of values, equivalent to: sorted(values)[k]. If this was implemented optimally, how fast could it run?

Answers are in BigO notation where n is the size of values.

1. O(n log n)

2.O(n)

3.O(n log k)

4.O(k log k)