# Modified Quickselect - Proving linear time

As we know, Quickselect chooses a 'random' element in order to partition the array around that element in every iteration.

Assume the random element is at most the $$\frac{1}{k}\cdot n$$ largest element, and at least the $$\frac{k-1}{k}\cdot n$$ largest element, for some constant $$k>1$$.

I'm asked to prove that under those terms, Quickselect will run in linear time.

Here is how far I've got:

We know that for each iteration, there exists $$r_i \in \mathbb{R}$$ such that: $$\frac{1}{k}\cdot n\leq r_i\cdot n \leq \frac{k-1}{k}\cdot n$$, this lets us know that: $$T(n)=T(r_1\cdot n)+O(n)$$

but also, we know that: $$T(n)\leq T(\frac{k-1}{k}\cdot n)+O(n)$$ I was not able to continue further than this, I'm aware that I need to reach some sort of summation equation.

• IMO, you swapped "at most" and "at least".
– user16034
Commented Apr 10, 2023 at 13:19
• Do you mean $\frac kn$ overall, or $\frac kn$ on every recursive call ?
– user16034
Commented Apr 10, 2023 at 14:31
• Thank you Yves, but this question is old and unfortunatly, I no longer remember the details of this, it seems I have forgot to mark it as 'completed'. Commented Apr 10, 2023 at 15:09

You can do it by proving by induction that there exists a constant $$A$$ such that for all $$n\geqslant 0$$, $$T(n) \leqslant Akn$$.
Note that the constant $$A$$ can be chosen depending on $$T(1)$$ and such that the $$\mathcal{O}(n)$$ in your relation is $$\leqslant An$$.
• I've tried this for quite some time yet this doesn't seem to help me prove. I'm stuck on understanding how to express every iteration using $T(n)$ What i've got is that: $$T(\frac{k-1}{k} \cdot n)=T(\frac{k-1}{k} \cdot \frac{k-1}{k} \cdot n)+O(\frac{k-1}{k} \cdot n)$$ I'm not sure how to move on from this, A colleague told me to find a way to turn this into a sum series, yet I'm not sure on how to do so, and what benefits will it get me. Commented Nov 11, 2022 at 14:40
• Use an induction: suppose that for all $m<n$, $T(m) \leqslant Akm$, and use it to prove $T(n) \leqslant Akn$. Commented Nov 11, 2022 at 14:59