1. **Problem Statement:** We are analyzing the average-case time complexity of the Quick-Select algorithm. The "good case" pivot is now defined as having index $i$ satisfying $$\frac{n}{3} \leq i < \frac{2n}{3}.$$ We want to find an upper bound for $$T(n)$$ and prove that Quick-Select runs in $$O(n)$$ under this new assumption. 2. **Calculate probabilities:** - Number of good case pivot positions: $$\frac{2n}{3} - \frac{n}{3} = \frac{n}{3}$$ - Total possible pivot positions: $$n$$ - Probability of good case: $$P(good) = \frac{n/3}{n} = \frac{1}{3}$$ - Probability of bad case: $$P(bad) = 1 - P(good) = \frac{2}{3}$$ 3. **Recurrence relations:** - In the good case, the pivot splits the problem such that the maximum size of recursive call is at most $$\frac{2n}{3}$$ - In the bad case, the recursive call could be of size as large as $$n-1 \approx n$$ So we model the expected running time $$T(n)$$ as: $$ T(n) \leq cn + P(good) T\left(\frac{2n}{3}\right) + P(bad) T(n) $$ where $$c$$ is a constant time spent partitioning. 4. **Rewrite to isolate $$T(n)$$:** $$ T(n) - \frac{2}{3} T(n) \leq cn + \frac{1}{3} T\left(\frac{2n}{3}\right) \\ \Rightarrow \frac{1}{3} T(n) \leq cn + \frac{1}{3} T\left(\frac{2n}{3}\right) \\ \Rightarrow T(n) \leq 3cn + T\left(\frac{2n}{3}\right) $$ 5. **Solve the recurrence:** Apply the recurrence repeatedly: $$ T(n) \leq 3cn + 3c \frac{2n}{3} + 3c \left(\frac{2}{3}\right)^2 n + \cdots = 3c n \left(1 + \frac{2}{3} + \left(\frac{2}{3}\right)^2 + \cdots\right) $$ This is a geometric series with ratio $$r=\frac{2}{3} < 1$$, sum: $$ \sum_{k=0}^{\infty} r^k = \frac{1}{1-r} = \frac{1}{1-\frac{2}{3}} = 3 $$ So we get $$ T(n) \leq 3c n \times 3 = 9cn = O(n) $$ 6. **Conclusion:** By choosing the good case as $$\frac{n}{3} \leq i < \frac{2n}{3}$$, the probability of good case is $$\frac{1}{3}$$. The resulting recurrence confirms that Quick-Select still runs in **linear time** on average, i.e., $$T(n) = O(n)$$.