Using Chernoff bound to analysis the Lazyselect algorithm

Question

It's my homework of the course of randomized algorithm. In the textbook (Randomized Altorithm by Rajeev Motwani et.al.), the author analyzed this algorithm using Chebyshev bound, but are there any ideas on how to analyze this algorithm using Chernoff bound? The LazySelect algorithm is presented as follows:

Input: A set of n elementss $S$ from a totally ordered universe, and an integer $k$ in$[1,n]$

output: The $k$th smallest element of $S,S(k)$

1. Pick $n^{3/4}$ elements from S,chosen independently and uniformly at random with replacement; call this multiset of elements R.
2. Sort R in $O($$n^{3/4}logn$$)$ steps using any optimal sorting algorithm.
3. Let $x=kn^{-1/4}$. For $l=max\{x-\sqrt n,1\}$ and $h=min\{x+\sqrt n,$$n^{3/4}$$\}$, let $a=R_l$ and $b=R_h$. By comparing a and b to every element of S, determine $r_s(a)$ and $r_s(b)$.

4. if $ k<n^{1/4}$, then $P=\{y∈S|y≤b\}$

   else if $ k>n-n^{1/4}$ ,let $P=\{y∈S|y≥a\}$;

   else if $k∈[n^{1/4},n-n^{1/4}]$, let $P=\{y∈S|a≤y≤b\}$;

   Check whether $S(k)∈P$ and $|P|≤4n^{3/4}+2$. If not, repeat Steps 1-3 until such a set P is found.

5. By sorting $P$ in $O(|P|\log|P|)$ steps, identify $P_{k-r_s(a)+1}$.

Answer 1

Using Chernoff bound to analyze this question is easy, you can just replace the Chebyshev method with Chernoff bound method. In fact, we can also decrease the number of samples for example at $O(\sqrt{n})$ samples. Poor English, forgive me!