Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

cs.stackexchange https://cs.stackexchange.com/questions/23811

Pergunta

In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented.

For its analysis, $T(n)$ is a random variable denoting the time required on an input array $A[p \cdots r]$ of $n$ elements and $X_k$ is an indicator random variable $X_k = I \{ \text{the subarray } A[p \cdots q] \text{ has exactly } k \text{ elements (due to the pivot)} \}$.

It has been claimed that $X_k$ and $T(\max(k-1, n-k))$ are independent (page 187 in the 2nd edition and page 218 in the 3rd edition). However, I find it quite counter-intuitive to understand. How to verify it?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top