Proof: Quick-Select Runs in Expected $O(n)$ Time

[evinda]

Hello! (Wave)

I am looking at the proof that the randomized quick-select algorithm runs in expected $O(n)$ time.

View attachment 4443

View attachment 4444

View attachment 4445

Could you explain me why the formula $t(n) \leq bn \cdot g(n)+t\left( \frac{3n}{4}\right)$ holds?

 

[Future Bruno]

The formula $t(n) \leq bn \cdot g(n)+t\left( \frac{3n}{4}\right)$ holds because the randomized quick-select algorithm makes a recursive call on a subarray of size $\frac{3n}{4}$, which means that the total running time must be bounded by the number of elements times the cost of each step plus the time needed for the recursive call. Specifically, it is bounded by $bn \cdot g(n)+t\left( \frac{3n}{4}\right)$, where $b$ is the cost of each step (which is constant) and $g(n)$ is the time to partition the array into subarrays (which is also constant).