-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ IMO, you swapped "at most" and "at least". $\endgroup$
    – user16034
    Commented Apr 10, 2023 at 13:19
  • $\begingroup$ Do you mean $\frac kn$ overall, or $\frac kn$ on every recursive call ? $\endgroup$
    – user16034
    Commented Apr 10, 2023 at 14:31
  • $\begingroup$ 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'. $\endgroup$
    – Aishgadol
    Commented Apr 10, 2023 at 15:09

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Aishgadol
    Commented Nov 11, 2022 at 14:40
  • $\begingroup$ Use an induction: suppose that for all $m<n$, $T(m) \leqslant Akm$, and use it to prove $T(n) \leqslant Akn$. $\endgroup$
    – Nathaniel
    Commented Nov 11, 2022 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.