Under the assumption that the QuickSelect algorithm always chooses a pivot that splits the array into two (almost) equal-sized partitions:

1. Write down the recurrence relation the describes how many times a return statement is executed for an array of length n.
2. Draw the recursion tree for this recurrence relation. For each node, indicate inside the node how many steps are executed by the paritioning step. Next to each node, indicate the size of the array at that point.
3. Use the recursion tree to solve the recurrence relation, that is, write down a big-Oh expression for the running time of this algorithm.