Well, here's what I came up with.
You could use Merge Sort, which has a worse-case time complexity of $O(n (log (n))$, then take the first 3 values of the array, but it felt like this question was seeking the use of the Randomized Select algorithm.
Best case for Randomized Select would be select $3$ (or $1$) as your random pivot and then make a comparison to the left or right of that for the other two spots, giving you a complexity of $n-1+1$ or $\Omega(n)$.
But this is asking for worst case. By my calculation if an adversary is always picking the furthest pivot from the target (say $k=3$), then the time complexity would be:
$$\frac{n(n-1)}{2} $$
For example. Let's say you have an unsorted array of $7,5,9,8$. The third smallest number is $8$ so the worst pivot is $5$. Compare $7,8,9$ (which is $n-1$ comparisons), you see there are 3 numbers greater.
The next worst pivot is either $7$ or $9$, so pick one of those, and $n-2$ comparisons, you see $8$ and $9$ are greater than 7. You know that $5$ is the smallest, $7$ is the second smallest, but you still need the third smallest. Repeat.
Pick $9$ as your pivot and make $n-3$ comparisons to see that $9$ is the 4th smallest, meaning $8$ is your 3rd smallest.
Add up those comparisons and simplify, you get the formula quoted above. Worst-case this seems less efficient than Merge Sort and selecting the first three numbers, but this seemed like the application of Randomized Select that the question was leaning toward (based on the book and classroom work).
Hope this helps someone else.
