Good and Bad Splits

To simplify our analysis of this recurrence, we will artificially divide the world into two categories.

• A good split is one in which $i+1/4\;(j-i+1) \le k \le j-1/4\;(j-i+1)$ .
• A bad split is one in which $i \le k < i+1/4\;(j-i+1)$ or $j-1/4\;(j-i+1)< k \le j$ .

The probability of a good split is 1/2 and the probability of a bad split is 1/2.