Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?
-
31-10-2019 - |
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