1. **State the problem:** We analyze the Quick-Select algorithm's average-case time complexity when the "good case" pivot lies in the middle third of the array, i.e., $\frac{n}{3} \leq i < \frac{2n}{3}$. 2. **Calculate the probability of the good case:** The good case range has length $\frac{2n}{3} - \frac{n}{3} = \frac{n}{3}$. Thus, the probability of choosing a good pivot is $$P(\text{good}) = \frac{n/3}{n} = \frac{1}{3}.$$ The probability of a bad case is $$P(\text{bad}) = 1 - P(\text{good}) = \frac{2}{3}.$$ 3. **Characterize recursive bounds:** In the good case, the pivot splits the array into parts with size at most $\frac{2n}{3}$. So, $$T(n) \leq T\left(\frac{2n}{3}\right) + cn,$$ where $c$ is a constant for partitioning cost. In the bad case, the pivot lies outside the middle third, so one partition could be as large as $n - 1$. Hence, $$T(n) \leq T(n - 1) + cn.$$ 4. **Formulate the expected time recurrence:** The expected time is $$E[T(n)] \leq P(\text{good}) T\left(\frac{2n}{3}\right) + P(\text{bad}) T(n - 1) + cn.$$ Substitute probabilities: $$E[T(n)] \leq \frac{1}{3} T\left(\frac{2n}{3}\right) + \frac{2}{3} T(n - 1) + cn.$$ 5. **Use induction to prove $E[T(n)] = O(n)$:** Assume for some constant $a$, $T(k) \leq a k$ for all $k < n$. Then $$E[T(n)] \leq \frac{1}{3} a \frac{2n}{3} + \frac{2}{3} a (n - 1) + cn = a n \left(\frac{2}{9} + \frac{2}{3}\right) - \frac{2a}{3} + cn.$$ Simplify coefficients: $$\frac{2}{9} + \frac{2}{3} = \frac{2}{9} + \frac{6}{9} = \frac{8}{9}.$$ So, $$E[T(n)] \leq \frac{8a}{9} n - \frac{2a}{3} + cn.$$ To satisfy $E[T(n)] \leq a n$, for large $n$, picking sufficiently large $a$ and $c$ ensures the inequality holds. Thus, $$E[T(n)] = O(n).$$ 6. **Conclusion:** Changing the good case to be $\frac{n}{3} \leq i < \frac{2n}{3}$ gives a smaller probability of good pivots ($\frac{1}{3}$ instead of $\frac{1}{2}$), but we still get an expected linear time bound for Quick-Select, i.e., $T(n) = O(n)$.