When doing Quick-Select and Quick-Select, it is desired to have a good pivot which is almost in the middle of the sorted array. When doing the average-case analysis of Quick-Select, we considered a good and a bad case; the good case happened when the pivot was among the half middle items of the sorted array, i.e., we had n/4 i < 3n/4 (i is the index of pivot in the partitioned array). In our analysis, we provided an upper bound for the time complexity of the algorithm in the good case and showed that T(n) T(3n/4) + cn in these cases for some constant c. Since the good case happened with probability 1/2, we could prove that the algorithm runs in linear time on average.

Change the definition of the good case and assume the good case happens when we have n/10 i < 9n/10. Provide an upper bound for T(n) and use that to show that Quick-Select runs in O(n).

Hint: start by calculating the probability of good case and bad case happening.