Analysis

The running time depends a lot on where k ends up. We call this the split.

If k is equal to i or j every time, we get

• T(n) = n + T(n-1); $T(n) = \Theta(n^2)$.

This is a very bad split.

If k is halfway between i and j, we get

• T(n) = n + 2 T(n/2); $T(n) = \Theta(n \log n)$.

This is a very good split.

In fact, it is possible to show that the running time is O(n²) and $\Omega(n\log n)$; these are the worst and best cases, respectively.